315. 计算右侧小于当前元素的个数

题目

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：

输入：nums = [-1]
输出：[0]

示例 3：

输入：nums = [-1,-1]
输出：[0,0]

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

想学习树状数组，来回顾一下这个题，这个题可以当做树状数组的入门例题。

代码

树状数组

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        // 首先离散化，可以节省树状数组空间
        // 下面一行代码对numns去重并排序
        // [6, 8, 5, 7, 5, 7, 1] 会得到 [1, 5, 6, 7, 8]
        int[] arr = Arrays.stream(nums).distinct().sorted().toArray();
        // 然后使用哈希表记录每个数的rank，key为arr元素，value为位次，越小的数位次越靠前
        // 1, 5, 6, 7, 8 位次分别是 1,2,3,4,5
        Map<Integer, Integer> map = new HashMap<>();
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            map.put(arr[i], i + 1);
        }
        List<Integer> ans = new ArrayList<>();
        FenwickTree fenwickTree = new FenwickTree(n);
        // 因为看右侧有多少数比自己小，因此倒着遍历
        for (int i = nums.length - 1; i >= 0; i--) {
            int num = nums[i];
            int rank = map.get(num);
            // 下面两行可以交换
            // 当前数排名为rank，那么查询tree数组中rank下标前面(不包括rank)有多少数，即查询rank-1的前缀和
            ans.add(fenwickTree.query(rank - 1));
            // 在tree中将rank加1
            fenwickTree.update(rank, 1);
        }
        Collections.reverse(ans);
        return ans;
    }
}
public class FenwickTree {
    private int[] tree;
    private int len;
    public FenwickTree(int n) {
        this.len = n;
        tree = new int[n + 1];
    }
    public FenwickTree(int[] nums) {
        this.len = nums.length + 1;
        tree = new int[this.len + 1];
        for (int i = 1; i <= len; i++) {
            update(i, nums[i]);
        }
    }
    public void update(int i, int delta) {
        while (i <= len) {
            tree[i] += delta;
            i += lowbit(i);
        }
    }
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);
        }
        return sum;
    }
    public static int lowbit(int x) {
        return x & (-x);
    }
}