Poison

315. Count of Smaller Numbers After Self

发表于 
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++];
            }
        }
    }
}
Reference

315. Count of Smaller Numbers After Self