[LeetCode] Count of Smaller Numbers After Self

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

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

?

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

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++;         }     } }