315 Count of Smaller Numbers After Self

Search…
315. Count of Smaller Numbers After Self​
1. Question
You are given an integer arraynumsand you have to return a newcountsarray. Thecountsarray has the property wherecounts[i]is the number of smaller elements to the right ofnums[i].
Example:
1
Given nums = [5, 2, 6, 1]
2
​
3
To the right of 5 there are 2 smaller elements (2 and 1).
4
To the right of 2 there is only 1 smaller element (1).
5
To the right of 6 there is 1 smaller element (1).
6
To the right of 1 there is 0 smaller element.
Copied!
Return the array[2, 1, 1, 0].
2. Implementation
(1) Merge Sort
1
class Solution {
2
    public List<Integer> countSmaller(int[] nums) {
3
        List<Integer> res = new ArrayList<>();
4
​
5
        if (nums == null || nums.length == 0) {
6
            return res;
7
        }
8
​
9
        int n = nums.length;
10
        // count[i]表示，在nums排序前，i位置上的数的count of smaller numbers
11
        int[] count = new int[n];
12
        // index存的是nums中每个数对应的位置，index[i]表示，在nums排序前，第i位置上的数在归并过程中的位置
13
        int[] index = new int[n];
14
​
15
        for (int i = 0; i < n; i++) {
16
            index[i] = i;
17
        }
18
​
19
        mergeSort(nums, index, count, 0, n - 1);
20
​
21
        for (int i : count) {
22
            res.add(i);
23
        }
24
        return res;
25
    }
26
​
27
    public void mergeSort(int[] nums, int[] index, int[] count, int start, int end) {
28
        if (start >= end) {
29
            return;
30
        }
31
​
32
        int mid = start + (end - start) / 2;
33
        mergeSort(nums, index, count, start, mid);
34
        mergeSort(nums, index, count, mid + 1, end);
35
        merge(nums, index, count, start, mid, end);
36
    }
37
​
38
    public void merge(int[] nums, int[] index, int[] count, int start, int mid, int end) {
39
        int[] temp = new int[end - start + 1];
40
​
41
        int i = start;
42
        int j = mid + 1;
43
        int k = 0;
44
        int rightCount = 0;
45
​
46
        while (i <= mid && j <= end) {
47
            // index[j]在归并排序的后半部分，如果nums[index[j]] < nums[index[i]] 说明index[j]所对应的数在nums中原本是在index[i]对应的数后面，而nums[index[j]] < nums[index[i]], 说明我们找到一个符合条件的count of smaller number, 所以rightCount加一
48
            if (nums[index[j]] < nums[index[i]]) {
49
                // 注意这里temp存储的是数字对应的位置，不是数字的值，这和传统的merge sort不同
50
                temp[k] = index[j];
51
                ++rightCount;
52
                ++j;
53
            }
54
            // 当nums[index[j]] >= nums[index[i]]时，因为index[i]对应的数在[index[j]对应的数前面，而index[i]的count of smaller number就是rightCount
55
            else {
56
                temp[k] = index[i];
57
                count[index[i]] += rightCount;
58
                ++i;
59
            }
60
            ++k;
61
        }
62
​
63
        while (i <= mid) {
64
            temp[k] = index[i];
65
            count[index[i]] += rightCount;
66
            ++k;
67
            ++i;
68
        }
69
​
70
        while (j <= end) {
71
            temp[k] = index[j];
72
            ++k;
73
            ++j;
74
        }
75
​
76
        // 将合并完成后的数组所对应的位置重新存放在index中
77
        for (int m = start; m <= end; m++) {
78
            index[m] = temp[m - start];
79
        }
80
    }
81
}
Copied!
3. Time & Space Complexity
merge sort: 时间复杂度O(nlong), 空间复杂度O(n)
296 Best Meeting Point
324 Wiggle Sort II
Last modified 2yr ago
Copy link
Contents
315. Count of Smaller Numbers After Self
1. Question
2. Implementation
3. Time & Space Complexity
315. Count of Smaller Numbers After Self​

1. Question

2. Implementation

3. Time & Space Complexity

315. Count of Smaller Numbers After Self
