题解 | #数组中的逆序对#(普通解法)

#include <iostream>
class Solution {
private:
    const int kmod = 1000000007;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    
    void mergeSort(int l,int r,vector<int>& tmp,vector<int> &nums,int &count){
        
        if (l>=r) {
            return;
        }
        int mid = l+r>>1;
        mergeSort(l, mid,tmp,nums,count);
        mergeSort(mid+1, r,tmp,nums,count);
        merge(l,r,mid,tmp,nums,count);
    }
    void merge(int l,int r,int mid,vector<int> &tmp,vector<int> &nums,int &count){
        int i = l,j = mid+1,k=0;
        while (i<=mid&&j<=r) {
            if (nums[i]<=nums[j]) {
                tmp[k++] = nums[i++];
            }
            else{
                tmp[k++] = nums[j++];
                count += (mid - i + 1);
                count %= kmod;
            }
        }
        while (i<=mid) {
            tmp[k++] = nums[i++];
        }
        while (j<=r) {
            tmp[k++] = nums[j++];
        }
        for (k=0,i = l; i<=r; i++,k++) {
            nums[i] = tmp[k];
        }
    }
    int InversePairs(vector<int>& nums) {
        int count = 0;
        vector<int> tmp(nums.size());
        mergeSort(0,nums.size()-1,tmp,nums,count);
        return count;
        // write code here
    }

};