题目描述

给定一个整数数组 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 个更小的元素。

算法

(离散化 + 树状数组) $O(n \log n)$

1. 首先将 nums 所有数字离散化到 1 到 n 中，离散化可以通过排序和 lower_bound 解决。
2. 然后从右向左扫描数组，每遇到一个数，在树状数组中查询 query(nums[i] - 1)，即树状数组中小于等于 nums[i] 位置的前缀和。
3. 然后更新树状数组 update(nums[i], 1)，即在 nums[i] 位置上加 1。

时间复杂度

• 离散化的时间复杂度为 $O(n \log n)$，树状数组每次操作的时间复杂度为 $O(\log n)$，故时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储离散化数组和树状数组。

C++ 代码

class Solution {
public:
    vector<int> f;
    int m;

    void update(int x, int y) {
        for(; x <= m; x += x & -x)
            f[x] += y;
    }

    int query(int x) {
        int tot = 0;
        for(; x; x -= x & -x)
            tot += f[x];
        return tot;
    }

    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> b(nums), ans(n);

        sort(b.begin(), b.end());
        m = unique(b.begin(), b.end()) - b.begin();
        b.resize(m);

        f = vector<int>(m + 1, 0);

        for (int i = 0; i < n; i++)
            nums[i] = lower_bound(b.begin(), b.end(), nums[i]) - b.begin() + 1;

        for (int i = n - 1; i >= 0; i--) {
            ans[i] = query(nums[i] - 1);
            update(nums[i], 1);
        }

        return ans;
    }
};