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)