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

class Solution {
    //1.logn次分割递归 每一层n次操作
    //2.辅助数组可以放排序数组 也可以先复制辅助数组原数组排序 递归传递引用数组
    //3.取模结果需要将count设置为long型 原数组数值只需要作比较int即可
public:    
    long mergesort(vector<int> &nums, vector<int> &temp, int left, int right){
        if(left==right){
            return 0;
        }//digui tingzhi tiaojian 
        int mid=(left+right)/2;
        long countl=mergesort(nums,temp,left, mid);
        long countr=mergesort(nums,temp,mid+1,right);
        long count=0;
        for(int i=left;i<=right;i++){
            temp[i]=nums[i];
        }//fuzhi 
        int i1=left, i2=mid+1;//double pointer
        for(int curr=left;curr<=right;curr++){
            if(i1==mid+1){
                nums[curr]=temp[i2++];//left over, copy right
            }
            else if(i2==right+1){
                nums[curr]=temp[i1++];
            }//right over, copy left
            else if(temp[i1]<temp[i2]){
                nums[curr]=temp[i1++];
            }
            else{
                nums[curr]=temp[i2++];
                count+=mid-i1+1;
            }
        }
        return countl+countr+count;
    }
    int InversePairs(vector<int>& nums) {
        vector<int>temp(nums.size());
        long re=mergesort(nums,temp,0,nums.size()-1);
        /*for(auto num:nums){
            cout<<num<<' ';
        }*/
        
        return re % 1000000007;
    }
};