315. Count of Smaller Numbers After Self - jiejackyzhang/leetcode-note GitHub Wiki

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[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].

##Approach 1: Binary Search

  • 从后至前扫描数组，并维护一个sorted数组，找出当前元素在sorted数组中的index，即为右边比它小的元素个数。 找index的过程可通过binary search完成。

time O(nlogn), space O(n)

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        List<Integer> sorted = new ArrayList<>();
        if(nums == null || nums.length == 0) return res;
        for(int i = nums.length-1; i >= 0; i--) {
            int index = findIndex(sorted, nums[i]);
            res.add(0, index);
            sorted.add(index, nums[i]);
        }
        return res;
    }
    
    private int findIndex(List<Integer> sorted, int target) {
        if(sorted.size() == 0) return 0;
        int start = 0, end = sorted.size()-1;
        if(sorted.get(start) >= target) return 0;
        if(sorted.get(end) < target) return end+1;
        while(start < end) {
            int mid = start + (end - start) / 2;
            if(sorted.get(mid) < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}

##Approach 2: Binary Index Tree basic idea of binary index tree

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if(nums == null || nums.length == 0) return res;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int num : nums) {
            if(num < min) min = num;
        }
        int[] nums2 = new int[nums.length];
        for(int i = 0; i < nums.length; i++) {
            nums2[i] = nums[i] - min + 1;
            if(nums2[i] > max) max = nums2[i];
        }
        int[] tree = new int[max+1];
        for(int i = nums2.length-1; i >= 0; i--) {
            res.add(0, get(nums2[i]-1, tree));
            update(nums2[i], tree);
        }
        return res;
    }
    
    private int get(int i, int[] tree) {
        int num = 0;
        while (i > 0) {
            num += tree[i];
            i -= i & (-i);
        }
        return num;
    }
    private void update(int i, int[] tree) {
        while (i < tree.length) {
            tree[i]++;
            i += i & (-i);
        }
    }
}
⚠️ **GitHub.com Fallback** ⚠️