[LeetCode 315] Count Of smaller

Solution:

1. 如果直接对数组求解，那么时间复杂度是O(n sqr)
2. 可以将数组reverse一次，这样的话，求到5的时候，1和2已经访问过了，而且已知是小于5的，直接可以得出答案。
3. 可以借助Binary Index Tree，利用prefix sum of frequency， 将数组中每个数转换成它的rank（第i小的数） ，并将该 rank出现的frequency作为Binary Index Tree中的sum数组。
4. 那么问题就转换成了，对数组根据其rank求其prefix sum of frequency

1. Binary Index Tree

• int[] sum = new int [n unique number count + 1]: 每个rank的frequency
• updateTree
• queryTree

2. 求解

1）Get SortedSet uniqueNumbers = new TreeSet<> (), 并用given numbers 初始化该UniqueNumbers
2）Get UniqueNumber vs Ranking map

Map<Integer, Integer> uniqueNums2Rank = new HashMap<> ();
        int rank = 0;
        
        for (int num : uniqueNums) {
            rank++;
            uniqueNums2Rank.put (num, rank);
        }

3. reverse numbers，然后对每个数，从Binary Index Tree中query (Rank - 1)。即求，在其之前出现的，rank比其小的数，出现的frequency之和，将其推入result；然后更新frequency table，即更新Binary Index Tree
4. reverse result （因为是基于reversed的numbers来求解的）

class FenwickTree {
    private int[] sum;
    public FenwickTree (int n) {
        sum = new int [n + 1];
    }
    
    public void updateTree (int i, int value) {
        while (i < sum.length) {
            sum [i] += value;
            i += i & -i;
        }
    }
    
    public int queryTree (int i) {
        int result = 0;
        
        while (i > 0) {
            result += sum [i];
            i -= i & -i;
        }
        
        return result;
    }
}

class Solution {
    public FenwickTree tree;
    
    
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<> ();
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        
        //1. create the fenwick tree
        tree = new FenwickTree (nums.length);
        
        //2. get the unique number set
        SortedSet<Integer> uniqueNums = new TreeSet<> ();
        for (int num : nums) {
            uniqueNums.add (num);
        }
        
        
        //3. get the unique number vs its rank map
        Map<Integer, Integer> uniqueNums2Rank = new HashMap<> ();
        int rank = 0;
        
        for (int num : uniqueNums) {
            rank++;
            uniqueNums2Rank.put (num, rank);
        }
        
        //4. trying to find the count of smaller number after self based on the frequency of each rank of number
        //4.1 Based on reverse sort
        
        for (int i = nums.length - 1; i >= 0; i--) {
            int currentRank = uniqueNums2Rank.get (nums [i]);
            int currentCountOfSmallerNumber = tree.queryTree (currentRank - 1);
            result.add (currentCountOfSmallerNumber);
            
            tree.updateTree (currentRank, 1);
        }
        
        //5. reverse the result, becasue it's based on the reversed numbers
        Collections.reverse (result);
        return result;
    }
}