刷题记录

Problem: 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] . 6/27/2018 update: Another approach is to use binary index tree. Use  [5, 2, 6, 1] as example 1. Get the ranks of sorted numbers. sorted: [1, 2, 5, 6] ranks<number, rank>: [1: 1 , 2 : 2 , 5 : 3 , 6: 4 ] 2. Distribute rank to BIT. If number 2 ranks 2, add 1 to index 2 of BIT. 3. Get sum of BIT before current rank If we reach 6, the rank is 4. Then we count how many numbers before rank 4. BIT helps to reduce the counting process to O(logN) instead of O(N). class Solution { int [] BIT; public List< Integer > countSmaller ( int [] nums) { Map< Integer , Integer > ranks = new HashMap<> (); List< Integer > res = new ArrayList<> (); BIT = new int [...