题目描述

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

示例:

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

算法1

(树状数组) $O(nlogn)$

我这边加了一个原始a数组，表示某个位置出现的数字的个数，更好看出a数组和c数组关系

Java 代码

class Solution {
    /**
     * BIT解法
     * @param nums
     * @return
     */
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        if (n == 0) {
            return res;
        }
        // [1,2,5,6]
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);

        HashMap<Integer/**原始数字**/, Integer/**离散化后的数字**/> ranks = new HashMap<>();
        for (int i = 0, rank = 0; i < sorted.length; i++) {
            if (i == 0 || sorted[i] != sorted[i - 1]) {
                ranks.put(sorted[i], ++rank);
            }
        }
        // nums  5,2,6,1
        // ranks 3,2,4,1
        BIT tree = new BIT(ranks.size());
        for (int i = nums.length - 1; i >= 0; --i) {
            Integer x = ranks.getOrDefault(nums[i], 0);
            // 小于x的前缀(区间)和a[1~3]
            int sum = tree.query(x - 1);
            res.add(sum);
            tree.update(x, 1);
        }
        Collections.reverse(res);
        return res;
    }

    class BIT {

        private int[] c;
        private int[] a;

        public BIT(int n) {
            c = new int[n + 1];
            a = new int[n + 1];
        }

        private void update(int i, int delta) {
            if (i >= 0 && i < c.length) {
                a[i] += delta;
            }
            while (i < c.length) {
                c[i] += delta;
                i += lowBit(i);
            }
        }

        private int query(int i) {
            int sum = 0;
            while (i > 0) {
                sum += c[i];
                i -= lowBit(i);
            }
            return sum;
        }
    }

    private int lowBit(int i) {
        return i & -i;
    }
}