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

class Solution {
public:
    void merge(vector<int>& nums,vector<int>& v,int left,int right,int mid,int& count)
    {
        int i=left,j=mid+1,k=0;
        while(i<=mid && j<=right)
        {
            if(nums[i] < nums[j])
            {
                v[k++] = nums[i++];
            }
            else 
            {
                count = (count+(mid-i+1))%1000000007;
                v[k++]=nums[j++];
            }
        }
        while(i<=mid)
        {
            v[k++] = nums[i++];
        }
        while(j<=right)
        {
            v[k++]=nums[j++];
        }
        k=0;
        while(left<=right)
        {
            nums[left++] = v[k++];
        }
    }
    void mergsort(vector<int>& nums,vector<int>& v,int left,int right,int& count)
    {
        if(left == right) return;
        else{
            int mid = left + ((right-left) >>1);
            mergsort(nums,v,left,mid,count);
            mergsort(nums,v,mid+1,right,count);
            merge(nums,v,left,right,mid,count);
        }
    }
    int InversePairs(vector<int>& nums) {
        // write code here
         int count=0, len=nums.size();
        vector<int> v(len); 
        mergsort(nums,v,0,len-1,count);
        return count;
    }
};