题解 | 数组中的逆序对

归并排序加上辅助数组，双指针快速统计并合并相邻有序数组的元素

#include <functional>
#include <vector>

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

        merge_sort(0,n-1);
        return result;
    }
    
};