Open
Description
题目
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 ofnums[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;
}
}