重温已经是小菜一碟。

只需在归并排序模版上加两行代码。

C++ 代码

class Solution {
public:
    int q[50010] = {0};
    int reversePairs(vector<int>& nums) {
        if(nums.size() < 2)
            return 0;
        return reverseP(nums, 0, nums.size() - 1);
    }
    int reverseP(vector<int>& nums, int l, int r){
        if(l >= r)return 0;
        int len = nums.size();
        int mid = (l + (r - l) / 2);
        int left = reverseP(nums, l, mid);
        int right = reverseP(nums, mid + 1, r);
        int i = l, j = mid + 1, sum = 0, k = 0;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j])
                q[k ++ ] = nums[i ++ ];
            else{
                q[k ++ ] = nums[j ++ ];
                sum += mid - i + 1;
            }
        }
        while(i <= mid)q[k ++ ] = nums[i ++ ];
        while(j <= r)q[k ++ ] = nums[j ++ ];
        i = l, k = 0;
        for(; i <= r; i ++ , k ++ ){
            nums[i] = q[k];
        }
        return left + right + sum;
    }
};