315. Count of Smaller Numbers After Self

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].

BST优化后面补充，留坑。

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