315 Count of Smaller Numbers After Self

多种解法， 还有BST，Binary Search， 都是nlgn

class Solution {
    int[] count;
    public List<Integer> countSmaller(int[] nums) {
        count = new int[nums.length];
        int[] index = new int[nums.length];
        for (int i = 0; i < nums.length; i++){
            index[i] = i;
        }

        mergeSort(nums, index, 0, nums.length - 1);

        List<Integer> ans = new ArrayList<>();
        for (int c : count){
            ans.add(c);
        }

        return ans;
    }

    private void mergeSort(int[] nums, int[] index, int start, int end){
        if (end <= start) return;

        int mid = start + (end - start) / 2;
        mergeSort(nums, index, start, mid);
        mergeSort(nums, index, mid + 1, end);

        merge(nums, index, start, end);
    }

    private void merge(int[] nums, int[] index, int start, int end){
        int leftIndex = start;
        int mid = start + (end - start) / 2;
        int rightIndex = mid + 1;
        int[] new_index = new int[end - start + 1];

        int rightCount = 0, totalIndex = 0;
        while (leftIndex <= mid && rightIndex <= end){
            if (nums[index[rightIndex]] < nums[index[leftIndex]]){
                new_index[totalIndex++] = index[rightIndex++];
                rightCount++;
            }
            else{
                count[index[leftIndex]] += rightCount;
                new_index[totalIndex++] = index[leftIndex++];
            }
        }

        while (leftIndex <= mid){
            count[index[leftIndex]] += rightCount;
            new_index[totalIndex++] = index[leftIndex++];
        }
        while (rightIndex <= end){
            new_index[totalIndex++] = index[rightIndex++];
        }

        for (int i = start; i <= end; i++){
            index[i] = new_index[i - start];
        }
    }


}