493.reverse-pairs.md

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

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

示例 1:

输入: [1,3,2,3,1]
输出: 2
示例 2:

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

注意:

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

---

算法思路

这道题 跟求逆序对数量比较相似，我们考虑用归并排序和树状数组实现

归并排序

class Solution {
public:
    int t[50010];
    typedef long long LL;
    int merge(vector<int>& nums, int l, int r){
        if (l >= r) return 0;
        int mid = l+r >> 1;
        int ans = merge(nums, l, mid) + merge(nums, mid+1, r);
        int i = l, j = mid+1, k = 0,pt = mid + 1;
        while (i <= mid && j <= r) {
            if (nums[i] < nums[j]) {
                // 对于每一个i,找到有几个j满足 nums[i] > 2*nums[j]
                while (pt <= r && (LL)nums[i] > (LL)2 * nums[pt]) pt++;
                ans += pt - mid - 1;
                t[k++] = nums[i++];
            }
            else t[k++] = nums[j++];
        }
        while (i <= mid) {
            while (pt <= r && (LL) nums[i] >  (LL)2 * nums[pt])pt++;
            ans += pt - mid - 1;
            t[k++] = nums[i++];
        }
        while (j <= r) t[k++] = nums[j++];
        for (int i = l, j = 0; i <=r; ) nums[i++] = t[j++];
        return ans;
    }

    int reversePairs(vector<int>& nums) {
        return merge(nums, 0, nums.size() -1);
    }
};

树状数组