题解 | #21年8月份练题总数#

归并排序 如果左边数组的当前值小于右边数组的当前值 那么右边数组的当前值可以和 左边数组的当前值的所有值构成逆序对 相加即可 注意取模不要爆int

const int mod = 1000000007;
class Solution {
public:
    int InversePairs(vector<int> data) {
        vector<int> tmp(data.size());
        return mergeSort(0, data.size()-1,data,tmp);
    }
    int mergeSort(int l,int r,vector<int>& nums,vector<int>& tmp){
        if(l >= r) return 0;
        int m = (l + r) / 2;
        int res = mergeSort(l, m, nums, tmp) + mergeSort(m+1,r,nums,tmp);
        int i = l , j = m + 1;
        for(int k = l;k <= r;k++) tmp[k] = nums[k];
        for(int k = l;k <= r;k++){
            if(i == m + 1) nums[k] = tmp[j++];
            else if(j == r + 1 || tmp[i] <= tmp[j]) nums[k] = tmp[i++];
            else{
                nums[k] = tmp[j++];
                res = (res % mod + (m - i + 1) % mod) % mod; //左数组长度
            }
        }
        return res;
    }
};