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

class Solution {
public:
    int nixu(vector<int> &nums,vector<int>& tmp,int l,int r,int &cnt_nixu){
        int mod = 1000000007;
        if(l >= r)
            return 0;
        int mid = (l + r)/2;
        int s1 = l,e1 = mid;
        int s2 = mid+1,e2 = r;

        nixu(nums,tmp,l,mid,cnt_nixu);
        nixu(nums,tmp,mid+1,r,cnt_nixu);
        int k = l; 
        while(s1 <= e1 && s2 <= e2){
            if(nums[s1] > nums[s2]){
                tmp[k++] = nums[s2++];
                cnt_nixu += (mid+1 - s1);
//归并排序时统计逆序对的个数，合并前两个数组已经有序，如果左数组//当前值大于右数组当前值，说明左数组当前值以及后面的数值都比右数组当前值大即构成逆序对，逆序对个数为mid+1 - s1,
//右数组首个位置减去左数组当前值位置
                cnt_nixu %= mod;
            }else{
                tmp[k++] = nums[s1++];
            }
        }
        while(s1 <= e1){
            tmp[k++] = nums[s1++];
        }
        while(s2 <= e2){
            tmp[k++] = nums[s2++];
        }
        for(int i=l;i<=r;i++)
        {
            nums[i] = tmp[i];
        } 
        return cnt_nixu;  
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int InversePairs(vector<int>& nums) {
        // write code here
        //归并方法 
        int len_nums = nums.size();
        vector<int> tmp(len_nums);
        int cnt_nixu = 0;
        nixu(nums,tmp,0,len_nums-1,cnt_nixu);
        return cnt_nixu;
    }
};

/*
https://zhuanlan.zhihu.com/p/166127615
https://zhuanlan.zhihu.com/p/124356219
*/