LeetCode315、计算右侧小于当前元素的个数（采用归并）_给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质:

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：
输入：nums = [-1]
输出：[0]

示例 3：
输入：nums = [-1,-1]
输出：[0,0]

提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104

此题我们也采用归并的方式来完成。

此题要求我们只能向后看，看后面的小于当前要判断的值

但是在这个题当中，我们不仅要在辅助数组当中保留原始数组的中的数据还要有索引数据，所以在这我们就可以直接在辅助数组当中直接存入索引，然后通过索引去输入数组中查询数据来进行大小的比较。

代码的演示和详细注释：

public class Demo315 {
    public static void main(String[] args) {
        int[] a = {5,2,6,1};
        List<Integer> b = countSmaller(a);
        System.out.println(b);
    }


    private static List<Integer> countSmaller(int[] nums) {
        int len = nums.length;
        List<Integer> res = new ArrayList<>(len); //创建一个List的变量

        int[] indexes = new int[len];         //记录原数组中的索引数组
        for (int i = 0; i < len; i++) {       //将索引填充到数组当中
            indexes[i] = i;
        }
        int[] temp = new int[len];      //设置一个全局的辅助数组
        int[] ans = new int[len];       //记录修改后的数组。在ArrayList上直接弄不太方便
        reversePairs(nums, 0, len - 1, indexes, temp, ans);

        for (int i = 0; i < len; i++) {//在最后给List导入数据，并最后返回数组
            res.add(ans[i]);
        }
        return res;
    }

    /**
     * 调用方法
     * @param nums 记录原数组
     * @param left 记录最左边的索引
     * @param right 记录最右边的索引
     * @param indexes 传递索引的数组
     * @param temp 传递辅助数组
     * @param ans 返回最终计算出来的数组
     */
    private static void reversePairs(int[] nums, int left, int right, int[] indexes, int[] temp, int[] ans) {
        if (left == right) {    //当左边和右边的索引一样的时候，就是分到只要一个的时候，结束方法
            return;           //并返回0
        }
        int mid = (right + left) / 2;
        //获得当前要排序数组的中间的索引(因为这个题给的数组长度在相加也还在int之类，所以直接加是可以的

        reversePairs(nums, left, mid, indexes, temp, ans);//先对左边的进行分组
        reversePairs(nums, mid + 1, right, indexes, temp, ans);//然后对右边的进行分组
        mergeAndCount(nums, left, mid, right, indexes, temp, ans);//给ans数值计算值
    }

    /**
     * 给ans所求的给结果
     * @param nums 原数组
     * @param left 左边的索引位置
     * @param mid 中间索引
     * @param right 右边的索引位置
     * @param indexes 保存索引的数组
     * @param temp 辅助数组
     * @param ans 记录最终结果的数组
     */
    private static void mergeAndCount(int[] nums, int left, int mid, int right, int[] indexes, int[] temp, int[] ans) {
        for (int i = left; i <= right; i++) {
            temp[i] = indexes[i];//给辅助数组赋索引值
        }

        //i,j,k都与上面图中的互相对应着
        int i = left;
        int j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                indexes[k] = temp[j];//这里进行的是数组索引的交换
                j++;
            } else if (j == right + 1) {
                indexes[k] = temp[i];
                i++;
                // j - mid - 1 ==>  right + 1 - mid -1 ==> right - mid;
                ans[indexes[k]] += (right - mid);
            } else if (nums[temp[i]] <= nums[temp[j]]) { //nums[temp[i]]通过索引在输入数组当中得到数据
                indexes[k] = temp[i];
                i++;
                // j - mid - 1 见图说为什么 (๑•̀ㅂ•́)و✧
                ans[indexes[k]] += (j - mid - 1);
            } else {
                indexes[k] = temp[j];
                j++;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

还是不太明白的话，可以看看这两篇：
一、java实现归并排序
二、剑指offer 51. 数组中的逆序对

欢迎大家在评论区交流