题解 | #数组中的逆序对#归并排序

tips：

• kmod用1e9+7表示，几个0就e几
• 在主函数InversePairs中创建辅助数组，避免在每次merge中都新建数组，减少空间占用

class Solution {

public:
    
    const int kmod = 1e9+7;
    int count  = 0;      
    int InversePairs(vector<int> data) {   
        int n = data.size();
        if(n < 2)
            return 0;
        vector<int> tmp(n);
        mergeSort(data,tmp,0,n-1);
        return count;
    }
    
    void mergeSort(vector<int>& nums,vector<int>&tmp,int l,int r){
        if(l >= r)
            return;
        int mid = l + ((r - l) >> 1);
        mergeSort(nums, tmp, l, mid);
        mergeSort(nums, tmp, mid+1, r);
        merge(nums,tmp,mid,l,r);
    }
    
    void merge(vector<int>&nums,vector<int>&tmp,int mid,int left,int right){
        int i = left;
        int j = mid+1;
        int idx = 0;
        
        while(i<=mid && j<=right){
            if(nums[i] > nums[j]){
                tmp[idx++] = nums[j++];
                count += (mid + 1 - i);
                count %= kmod;
            }
            else
                tmp[idx++] = nums[i++];
        }
        while(i<=mid)
            tmp[idx++] = nums[i++];
        while(j<=right)
            tmp[idx++] = nums[j++];
        for(idx = 0, i = left ; i <= right; i ++,idx++)
            nums[i] = tmp[idx];
    }
};