算法题:计算右侧小于当前元素的个数

Scroll Down

题目描述:给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例

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

这道题目当时第一眼看到的时候脑子里毫无头绪,对于这种,当时第一反应呢是用Hash,后面发现怎么也Ha不出来就很头大,后面又想到了排序,排序呢会发现原数组的值的位置要变,发现这也行不通,后面看了题解,发现有索引数组这个东西,才用排序的思想(归并排序)给写出来,这道题呢,很像以前写过的一道经典面试题,逆序对,融合一下,用到索引数组就可以解出来了。

索引数组:开辟一个新的数组,用来记录原数组的索引
使用:根据这些索引,可以找到原数组的值,根据原数组的值来对索引数组进行操作,就可以达到我们想要的,原数组元素不动。

代码如下:

  public static int[] mergeOrder(int low, int high, int[] nums, int[] index, int[] res) {
        if (low == high) return new int[]{index[low]};

        int mid = (low + high) / 2;
        int[] leftArr = mergeOrder(low, mid, nums, index, res);
        int[] rightArr = mergeOrder(mid + 1, high, nums, index, res);
        int[] union = new int[leftArr.length + rightArr.length];


        int x = leftArr.length - 1, y = rightArr.length - 1, z = union.length - 1;
//逆序对的思想,不清楚的可以去看剑指Offer51题。
        while (x >= 0 && y >= 0) {
            if (nums[leftArr[x]] > nums[rightArr[y]]) {
                res[leftArr[x]] += y + 1;
                union[z--] = leftArr[x--];
            } else {
                union[z--] = rightArr[y--];
            }
        }
        while (y >= 0)
            union[z--] = rightArr[y--];
        while (x >= 0)
            union[z--] = leftArr[x--];

        return union;
    }


    private static List<Integer> getAnswer(int[] nums) {
        if (nums.length < 1) return new ArrayList<>();
        List<Integer> list = new ArrayList<>();
//索引数组
        int[] index = new int[nums.length];
//记录索引
        for (int i = 0; i < nums.length; i++) {
            index[i] = i;
        }
//结果数组
        int[] res = new int[nums.length];
        mergeOrder(0, nums.length - 1, nums, index, res);

        for (int val : res) {
            list.add(val);
        }
        return list;
    }

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self