题解 | 数组中的逆序对

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
long long merge(vector<int>&nums,vector<int>&temp,int left,int mid,int right)
{
    int i=left;
    int j=mid+1;
    int k=left;
    long long count=0;

    while(i<=mid&&j<=right)
    {
        if(nums[i]<=nums[j])
        {
            temp[k++]=nums[i++];
        }
        else 
        {
            temp[k++]=nums[j++];
            count+=mid-i+1;
        }
    }

    while(i<=mid) temp[k++]=nums[i++];
    while(j<=right) temp[k++]=nums[j++];

    for(int i=left;i<=right;i++)
    {
        nums[i]=temp[i];
    }
    return count;
}
     long long mergesort(vector<int>& nums,vector<int>&temp,int left,int right)
     {
        long long count=0;

        if(left<right)
        {
            int mid=(left+right)/2;
            count+=mergesort(nums,temp,left,mid);
            count+=mergesort(nums,temp,mid+1,right);
            count+=merge(nums,temp,left,mid,right);
        }
        return count;
     }
     const int mod=1000000007;
    int InversePairs(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int> temp(nums.size());
        long long count=mergesort(nums,temp,0,nums.size()-1);
        return count%mod;
   }
};