题解 | #数组中的逆序对#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    const int mod=1000000007;
    int MergeSort(int left,int right,vector<int>& data,vector<int>& temp)
    {
        if(left>=right)
            return 0;
        int mid=(left+right)/2;
        int res=MergeSort(left,mid,data,temp)+MergeSort(mid+1,right,data,temp);
        res%=mod;
        int i=left,j=mid+1;
        for(int k=left;k<=right;k++)
            temp[k]=data[k];
        for(int k=left;k<=right;k++)
        {
            if(i==mid+1)
                data[k]=temp[j++];
            else if(j==right+1||temp[j]>temp[i])
                data[k]=temp[i++];
            else
            {
                res+=mid-i+1;
                data[k]=temp[j++];
                res%=mod;
            }
        }
        return res;
    }
    int InversePairs(vector<int>& nums) {
        vector<int> temp(nums.size());
        return MergeSort(0,nums.size()-1,nums,temp);
    }
};