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
| class Solution {
private static class Element {
private final int value;
private final int index;
public Element(int value, int index) {
this.value = value;
this.index = index;
}
}
public List<Integer> countSmaller(int[] nums) {
Element[] elements = new Element[nums.length];
for (int i = 0; i < nums.length; i++) {
elements[i] = new Element(nums[i], i);
}
List<Integer> resultList = new ArrayList<>(Collections.nCopies(nums.length, 0));
Element[] tmp = new Element[nums.length];
mergeSort(elements, tmp, resultList, 0, nums.length - 1);
return resultList;
}
private void mergeSort(Element[] elements, Element[] tmp, List<Integer> resultList, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) >>> 1;
mergeSort(elements, tmp, resultList, left, mid);
mergeSort(elements, tmp, resultList, mid + 1, right);
for (int k = left; k <= right; k++) {
tmp[k] = elements[k];
}
int i = left, j = mid + 1;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {
elements[k] = tmp[j++];
} else if (j == right + 1) {
elements[k] = tmp[i++];
} else if (tmp[i].value > tmp[j].value) {
resultList.set(tmp[i].index, resultList.get(tmp[i].index) + right - j + 1);
elements[k] = tmp[i++];
} else {
elements[k] = tmp[j++];
}
}
}
}
|