315 Count of Smaller Numbers After Self

315. Count of Smaller Numbers After Self

1. Question

You are given an integer arraynumsand you have to return a newcountsarray. Thecountsarray has the property wherecounts[i]is the number of smaller elements to the right ofnums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array[2, 1, 1, 0].

2. Implementation

(1) Merge Sort

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();

        if (nums == null || nums.length == 0) {
            return res;
        }

        int n = nums.length;
        // count[i]表示，在nums排序前，i位置上的数的count of smaller numbers
        int[] count = new int[n];
        // index存的是nums中每个数对应的位置，index[i]表示，在nums排序前，第i位置上的数在归并过程中的位置
        int[] index = new int[n];

        for (int i = 0; i < n; i++) {
            index[i] = i;
        }

        mergeSort(nums, index, count, 0, n - 1);

        for (int i : count) {
            res.add(i);
        }
        return res;
    }

    public void mergeSort(int[] nums, int[] index, int[] count, int start, int end) {
        if (start >= end) {
            return;
        }

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

    public void merge(int[] nums, int[] index, int[] count, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];

        int i = start;
        int j = mid + 1;
        int k = 0;
        int rightCount = 0;

        while (i <= mid && j <= end) {
            // index[j]在归并排序的后半部分，如果nums[index[j]] < nums[index[i]] 说明index[j]所对应的数在nums中原本是在index[i]对应的数后面，而nums[index[j]] < nums[index[i]], 说明我们找到一个符合条件的count of smaller number, 所以rightCount加一
            if (nums[index[j]] < nums[index[i]]) {
                // 注意这里temp存储的是数字对应的位置，不是数字的值，这和传统的merge sort不同
                temp[k] = index[j];
                ++rightCount;
                ++j;
            }
            // 当nums[index[j]] >= nums[index[i]]时，因为index[i]对应的数在[index[j]对应的数前面，而index[i]的count of smaller number就是rightCount
            else {
                temp[k] = index[i];
                count[index[i]] += rightCount;
                ++i;
            }
            ++k;
        }

        while (i <= mid) {
            temp[k] = index[i];
            count[index[i]] += rightCount;
            ++k;
            ++i;
        }

        while (j <= end) {
            temp[k] = index[j];
            ++k;
            ++j;
        }

        // 将合并完成后的数组所对应的位置重新存放在index中
        for (int m = start; m <= end; m++) {
            index[m] = temp[m - start];
        }
    }
}

3. Time & Space Complexity

merge sort: 时间复杂度O(nlong), 空间复杂度O(n)