315. Count of Smaller Numbers After Self

[LLancelot]

题目

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:

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.

这道题与307. Range Sum Query – Mutable 类似，可以用 Fenwick Tree (Binary Indexed Tree) 这种特殊的数据结构来处理。具体参考 Fenwick Tree

首先定义 Fenwick Tree 的类：

• int query(int i); 方法用来查找第i个节点的prefix sum，求 prefix sum 的过程是沿着一条路径（如图），每次 i -= i & -i; 并将 prefix sum 累加。
• void update(int i, int delta); 方法用来动态更新第i个节点的值sums[i]，以及受它影响的其他节点的值（如图），至于是哪些节点（哪些 index）受影响，操作跟query相反，每次i += i & -i;并更改sums[i].

class FenwickTree {    
    private int[] sums;    
    
    public FenwickTree(int n) {
      sums = new int[n + 1];
    }
 
    public void update(int i, int delta) {    
      while (i < sums.length) {
          sums[i] += delta;
          i += lowbit(i); //             i += i & -i;
      }
    }
 
    public int query(int i) {       
      int sum = 0;
      while (i > 0) {
          sum += sums[i];
          i -= lowbit(i); //             i += i & -i;
      }
      return sum;
    }    
}

然后，根据题意，我们要求解 [5, 2, 6, 1] 中，比自己要小的后续数字个数 (smaller numbers after self)，第一个数是5，后面的2、1比5小，所以有2个；第二个数是2，后面的1比2小，有1个；以此类推。

基本思路：

• 先将原数组排序，用HashMap记录排序后数字的相对排名(rank，数越大排名越大)，根据 rank 我们可以知道两点：1. 有多少个unique numbers， 2. 根据 rank 个数（也就是不重复数字的个数）创建一个辅助数组，该数组下标代表数组对应的排名，也就是说，假如先访问的数字比较小，对应的下标在 rank[] 中就靠前，那么我们query这个数组的范围（0 到 i）就小，再update。如果后面访问的数字越来越大，对应的下标在 rank[] 中就靠后，那么我们只需要找排名比它要小的数字（rank范围在0到i）的总数即可，这个总数可以看成 rank[] 的前缀和 prefix sum。所以核心思路就是要先记录较小数字出现的次数，并保证记录的时候要在辅助数组（rank数组）中靠前，那么问题就转化为求一个数组前i个元素的前缀和了，凡是求 prefix sum的问题，也都能用 fenwick tree 解决了。

完整代码：

class FenwickTree {    
    int[] sums;
    
    public FenwickTree(int n) {
        // constructor
        sums = new int[n + 1];
    }
    
    public void update(int i, int delta) {
        while (i < sums.length) {
            sums[i] += delta;
            i += i & -i; // 等号右边取lowbit(i)，最低位二进制数
        }
    }
    
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += sums[i];
            i -= i & -i;
        }
        return sum;
    }
}

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        Map<Integer, Integer> ranks = new HashMap<>(); // map<num, rank>
        int rank = 0;
        for (int i = 0; i < sorted.length; i++) {
            if (i == 0 || sorted[i] != sorted[i - 1])
                ranks.put(sorted[i], ++rank);
        }
        
        FenwickTree tree = new FenwickTree(ranks.size());
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = nums.length - 1; i >= 0; --i ) { // 从后往前，保证先记录后面数字的rank[i]
            int prefix_sum = tree.query(ranks.get(nums[i]) - 1);
            ans.add(prefix_sum);
            tree.update(ranks.get(nums[i]), 1);
        }
        
        Collections.reverse(ans); // 因为是从后往前访问，最后记得反转ans
        return ans;
    }
}

[ytp327]

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def mergeSort(indexes):
            half = len(indexes) // 2
            if half:
                left, right = mergeSort(indexes[:half]), mergeSort(indexes[half:])
                for i in range(len(indexes))[::-1]:
                    if not right or left and nums[left[-1]] > nums[right[-1]]:
                        res[left[-1]] += len(right)
                        indexes[i] = left.pop()
                    else:
                        indexes[i] = right.pop()
            return indexes
        res = [0] * len(nums)
        mergeSort([i for i in range(len(nums))]) # merge sort the indexes
        return res