题目描述

给定一个数组 nums，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个 重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

样例

输入：[1,3,2,3,1]
输出：2

输入：[2,4,3,5,1]
输出：3

注意

• 给定数组的长度不会超过 50000。
• 输入数组中的所有数字都在 32 位整数的表示范围内。

算法

(树状数组) $O(n \log n)$

1. 首先将 nums 中的数字和每个数字的 2 倍统一进行离散化到 [1, 2n]。
2. 接下来仿照求逆序对的思路，从数组最后开始往前遍历，遍历过程中，在树状数组中查找小于等于 nums[i] 离散化后的值 x 再减 1 的个数。然后将 nums[i]*2 离散化后的值加入到树状数组中。

时间复杂度

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

空间复杂度

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

C++ 代码

class Solution {
public:
    #define LL long long
    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;
    }

    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<LL> b(2 * n);

        for (int i = 0; i < n; i++) {
            b[i] = nums[i];
            b[i + n] = (LL)(nums[i]) * 2;
        }
        sort(b.begin(), b.end());

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

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

        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            int x = lower_bound(b.begin(), b.end(), nums[i]) - b.begin() + 1;
            ans += query(x - 1);
            int y = lower_bound(b.begin(), b.end(), (LL)(nums[i]) * 2) - b.begin() + 1;
            update(y, 1);
        }

        return ans;
    }
};