leetcode 315 Count of Smaller Numbers After Self
z
 2019-04-08 10:18:26  

You are given an integer array nums and you have to return a new countsarray. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

1
2
3
4
5
6
7
Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
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.

basic idea:

  • 对数组进行mergesort，每次将left数组和right数组合并成一个数组

  • 在合并的时候，当这个数是从right数组过来的时候，那么这以后，从left过来的数的count就要加上1.

  • 当合并的数是从left过来的时候，把left对应的counts[i]加上count

  • 在merge的时候，不用对原始的nums进行merge，只需要对nums对应的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
49
50
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int[] res = new int[nums.length];
        int[] idx = new int[nums.length];
        for (int i=0; i<nums.length; i++) idx[i] = i;
        mergeSort(nums, res, idx, 0, nums.length-1);
        List<Integer> ans = new ArrayList<>();
        for (int i: res) {
            ans.add(i);
        }
        return ans;
    }
    
    public void mergeSort(int[] nums, int[] res, int[] idx, int left, int right) {
        if (right <= left) {
            return ;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, res, idx, left, mid);
        mergeSort(nums, res, idx, mid+1, right);
        merge(nums, res, idx, left, mid, mid+1, right);
    }
    
    public void merge(int[] nums, int[] res, int[] idx, int l1, int r1, int l2, int r2) {
        int[] temp = new int[r2-l1+1];
        int count = 0;
        int t = 0;
        int start = l1;
        while ( l1 <= r1 || l2 <= r2) {
            if (l1 > r1) {
                temp[t++] = idx[l2++];
            }
            else if (l2 > r2) {
                res[idx[l1]] += count;
                temp[t++] = idx[l1++];
            }
            else if (nums[idx[l1]] > nums[idx[l2]]) {
                temp[t++] = idx[l2++];
                count ++;
            }
            else {
                res[idx[l1]] += count;
                temp[t++] = idx[l1++];
            }
        }
        for (int i=0; i<temp.length; i++) {
            idx[start+i] = temp[i];
        }
    }
}