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

class Solution {
public:
    //本题其实就是小和问题，即求一个数后面有多少个数比他小
    //所以归并排序可以很好地解决这个问题
    //该递归函数的含义为对数组arr在L到R上排序，并返回逆序对个数
    int process(vector<int> &arr,int L, int R)
    {
        if(L==R)//base case,此时不用排序且逆序对个数为0
            return 0;
        int mid=(R+L)/2;//去中间位置,将数组一分为二，对左边排序，对右边排序，然后再合并两个有序数组
        long long res=0;//记录逆序对的个数
        res+=process(arr, L, mid);
        res%=1000000007;
        res+=process(arr, mid+1, R);
         res%=1000000007;
        //对左右两个有序数组进行合并，并且记录逆序对的个数
        //合并两个有序数组利用双指针算法
        int *help=new int[R-L+1];//定义一个辅助数组help
        for(int i=0;i<R-L+1;i++)
            help[i]=0;
        int index=0;//专门给辅助数组使用
        int left=L,right=mid+1;//左右两个指针
        while(left<=mid&&right<=R){
            if(arr[left]<arr[right]){//此时不会产生逆序对
                help[index]=arr[left];
                index++;
                left++;
            }
            //因为题目说了不会有重复数字，所以直接else即可
            else{//此时会产生逆序对
                help[index]=arr[right];
                //总共会产生多少个逆序对？
                index++;
                right++;
                res+=mid-left+1;//会产生这么多个逆序对
                 res%=1000000007;
                }
            }
        
        while(left<=mid){
            help[index++]=arr[left++];
        }
        while(right<=R){
            help[index++]=arr[right++];
        }
        //然后把help数组的值赋值给arr数组
        int ans=L;
        for(int i=0;i<index;i++){
            arr[ans++]=help[i];
        }
        return  res%=1000000007;;
    }
    int InversePairs(vector<int> data) {
       int res= process(data, 0, data.size()-1);
        return res%1000000007;
    }
};