[LeetCode] Count of Smaller Numbers After Self

参考：https://leetcode.com/discuss/73256/mergesort-solution

就是用merge sort，写完了看了这个才发觉自己二了，不需要用HashMap来存“比某个index的数小的数”的个数，用数组够了。

public class Solution {

    public List<Integer> countSmaller(int[] nums) {

        List<Integer> countOfSmallerNumbers = new ArrayList<Integer>();

        if (nums == null || nums.length == 0) return countOfSmallerNumbers;

        int[] indexTrack = new int[nums.length];
        HashMap<Integer, Integer> smallerNumberTrack = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            indexTrack[i] = i;
            smallerNumberTrack.put(i, 0);
        }
       
        mergeSort(nums, indexTrack, 0, nums.length - 1, smallerNumberTrack);
      
        for (int i = 0; i < nums.length; i++) {
            countOfSmallerNumbers.add(smallerNumberTrack.get(i));
        }
       
        return countOfSmallerNumbers;
    }   

    private void mergeSort(int[] nums, int[] indexTrack, int start, int end, HashMap<Integer, Integer> smallerNumberTrack) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        mergeSort(nums, indexTrack, start, mid, smallerNumberTrack);
        mergeSort(nums, indexTrack, mid + 1, end, smallerNumberTrack);

        int[] left = new int[mid - start + 1];
        int[] right = new int[end - mid];
        for (int i = 0; i <= mid - start; i++) left[i] = indexTrack[start + i];
        for (int i = 0; i < end - mid; i++) right[i] = indexTrack[mid + 1 + i];

        int leftIndex = 0, rightIndex = 0, current = start;
        while (current <= end) {
            if (rightIndex >= end - mid || (leftIndex <= mid - start && nums[left[leftIndex]] <= nums[right[rightIndex]])) {
                smallerNumberTrack.put(left[leftIndex], smallerNumberTrack.get(left[leftIndex]) + rightIndex);
                indexTrack[current] = left[leftIndex++];
            }
            else {
                indexTrack[current] = right[rightIndex++];
            }
            current++;
        }
    }
}