ChunNote
0%

leetCode-315:Count of Smaller Numbers After Self

发表于 分类于

问题描述

给定一个整数数组，要求输出一个数组，结果数组中的每个元素表示原始数组该位置后续元素比该位置元素小的元素数量。题目链接：点我

样例输入输出

输入：nums = [5,2,6,1]

输出：[2,1,1,0]

解释：原始数组中第一个元素 5，后续元素比他小的有两个：2 和 1，所以结果数组中第一个元素是 2

原始数组中第二个元素 2，后续元素比他小的有一个： 1，所以结果数组中第二个元素是 1

原始数组中第三个元素 6，后续元素比他小的有一个： 1，所以结果数组中第三个元素是 1

原始数组中第四个元素 1，没有后续元素，所以结果数组中第四个元素是 0

输入：nums = [-1]

输出：[0]

问题解法

按照题目意思，此题最简单的做法是两层循环分别计算结果，但是这样明显会超时，所以需要寻求更优的解法。

首先，先对数组进行排序去重，然后从后往前遍历数组，每次计算更新当前元素值的数量，同时计算获取小于当前元素值的数量。举例如下，假设数组 nums = [7, 5, 6, 5, 2, 6, 5, 1] ，则其计算步骤如下：

首先对数组排序去重，得到数组 [1, 2, 5, 6, 7]，然后从后往前遍历原始数组，分别计算数组元素出现的个数，同时计算小于该元素的元素数量。

当 i = 7 时（原始数组最后一个元素），此时元素为 1 ，更新数组如下，比 1 小的元素个数和为 0（表中没有比 1 小的元素），此时 counts[7] = 0

数组 n[j] 1 2 5 6 7
个数 c[j] 1 0 0 0 0

当 i = 6 时，此时元素为 5，更新数组如下，比 5 小的元素有 1 和 2，其个数分别为 1 和 0，相加得到值 1，counts[6] = 1

数组 n[j] 1 2 5 6 7
个数 c[j] 1 0 1 0 0

当 i = 5 时，此时元素为 6，更新数组如下，比 6 小的元素有 1 、 2、5，其个数分别为 1 、 0、1，相加得到值 1，counts[5] = 2

数组 n[j] 1 2 5 6 7
个数 c[j] 1 0 1 1 0

当 i = 4 时，此时元素为 2，更新数组如下，比 2 小的元素有 1，其个数为 1，counts[4] = 1

数组 n[j] 1 2 5 6 7
个数 c[j] 1 1 1 1 0

当 i = 3 时，此时元素为 5，更新数组如下，比 5 小的元素有 1 和 2，其个数分别为 1 和 1，相加得到值 2，counts[4] = 2

数组 n[j] 1 2 5 6 7
个数 c[j] 1 1 2 1 1

当 i = 2 时，此时元素为 6，更新数组如下，比 6 小的元素有 1 、 2、5，其个数分别为 1 、 1、2，相加得到值 4，counts[3] = 4

数组 n[j] 1 2 5 6 7
个数 c[j] 1 1 2 2 0

当 i = 1 时，此时元素为 5，更新数组如下，比 5 小的元素有 1 和 2，其个数分别为 1 和 1，相加得到值 2，counts[1] = 2

数组 n[j] 1 2 5 6 7
个数 c[j] 1 1 3 2 0

当 i = 0 时，此时元素为 7，更新数组如下，比 7 小的元素有 1 、 2、5、6，其个数分别为 1 、 1、3、2，相加得到值 7，counts[0] = 7

数组 n[j] 1 2 5 6 7
个数 c[j] 1 1 3 2 1

最终得到的结果数组为 [7, 2, 4, 2, 1, 2, 1, 0]

上述方法虽然可以得到结果，但是仍然效率低下。仔细观察可以发现，每次在计算个数时，都对元素之前的个数进行了汇总，这就是求前缀和或区间和，可以用树状数组来优化。此做法参考：https://leetcode.cn/problems/count-of-smaller-numbers-after-self/solutions/325800/shu-zhuang-shu-zu-de-xiang-xi-fen-xi-by-yangbingji

还是上面的例子，用树状数组计算的过程如下

当 i = 7 时（原始数组最后一个元素），此时元素为 1 ，对应树状数组下标为 1，更新树状数组C[1]、C[2]、C[4]，计算前缀和 sum[j - 1] = sum[0] = 0， counts[7] = 0

数组 n[j] 1 2 5 6 7
树状数组C[j] 1 1 0 1 0
树状数组下标 1 2 3 4 5

当 i = 6 时，此时元素为 5，对应树状数组下标为 3，更新树状数组 C[3]、C[4]，计算前缀和 sum[j - 1] = sum[2] = C[2] = 1，counts[6] = 1

数组 n[j] 1 2 5 6 7
树状数组C[j] 1 1 1 2 0
树状数组下标 1 2 3 4 5

当 i = 5 时，此时元素为 6，对应树状数组下标为 4，更新树状数组 C[4]，计算前缀和 sum[j - 1] = sum[3] = C[3] + C[2] = 2，counts[5] = 2

数组 n[j] 1 2 5 6 7
树状数组C[j] 1 1 1 3 0
树状数组下标 1 2 3 4 5

当 i = 4 时，此时元素为 2，对应树状数组下标为 2，更新树状数组 C[2]、C[4]，计算前缀和 sum[j - 1] = sum[1] = C[1] = 1，counts[4] = 1

数组 n[j] 1 2 5 6 7
树状数组C[j] 1 2 1 4 0
树状数组下标 1 2 3 4 5

当 i = 3 时，此时元素为 5，对应树状数组下标为 3，更新树状数组 C[3]、C[4]，计算前缀和 sum[j - 1] = sum[2] = C[2] = 2，counts[4] = 2

数组 n[j] 1 2 5 6 7
树状数组C[j] 1 2 2 5 0
树状数组下标 1 2 3 4 5

当 i = 2 时，此时元素为 6，对应树状数组下标为 4，更新树状数组 C[4]，计算前缀和 sum[j - 1] = sum[3] = C[3] + C[2] = 4，counts[3] = 4

数组 n[j] 1 2 5 6 7
树状数组C[j] 1 2 2 6 0
树状数组下标 1 2 3 4 5

当 i = 1 时，此时元素为 5，对应树状数组下标为 3，更新树状数组 C[3]、C[4]，计算前缀和 sum[j - 1] = sum[2] = C[2] = 2，counts[1] = 2

数组 n[j] 1 2 5 6 7
树状数组C[j] 1 2 3 7 0
树状数组下标 1 2 3 4 5

当 i = 0 时，此时元素为 7，对应树状数组下标为 5，更新树状数组C[5]，计算前缀和 sum[j - 1] = sum[4] = C[4] = 7，counts[0] = 7

数组 n[j] 1 2 5 6 7
树状数组C[j] 1 2 3 7 1
树状数组下标 1 2 3 4 5

最终得到的结果数组为 [7, 2, 4, 2, 1, 2, 1, 0]

代码如下

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
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> numList = Arrays.stream(nums).distinct().sorted().boxed().collect(Collectors.toList());
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numList.size(); i++) {
            map.put(numList.get(i), i + 1);    // 错位，留出下标为 0 的位置，方便后续树状数组计算更新
        }

        int[] sums = new int[numList.size() + 1];
        int[] counts = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int index = map.get(nums[i]);
            update(sums, index);
            counts[i] = querySum(sums, index - 1);
        }

        return Arrays.stream(counts).boxed().collect(Collectors.toList());
    }

    private int lowBit(int n) {
        return n & (-n);
    }

    private void update(int[] sums, int i) {
        for (int j = i; j < sums.length; j += lowBit(j)) {
            sums[j]++;
        }
    }

    private int querySum(int[] sums, int i) {
        int result = 0;
        while (i > 0) {
            result += sums[i];
            i -= lowBit(i);
        }

        return result;
    }
}

参考资料

https://leetcode.cn/problems/count-of-smaller-numbers-after-self/solutions/325800/shu-zhuang-shu-zu-de-xiang-xi-fen-xi-by-yangbingji/