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

class Solution {
private:
    vector<int> vv;
public:
    long int fun(vector<int>& nums,int low,int high)
    {
        if(low>=high)
            return 0;
        int mid = (low+high)/2;
        long left_count = fun(nums,low,mid);
        long right_count = fun(nums,mid+1,high);
        long mid_count = 0;
        int i=low,j=mid+1;
        int vvi=0;
        while(i<=mid && j<= high)
        {
            if(nums[i]< nums[j])
            {
                vv[vvi++] = nums[i++];
            }
            else {
                vv[vvi++] = nums[j++];
                mid_count += mid - i +1; // 核心
            }
        }
        while(i<=mid)
            vv[vvi++] = nums[i++];
        while(j<=high)
            vv[vvi++] = nums[j++];
            
        
        for(i=low,vvi=0;i<=high;i++)
        {
            nums[i] = vv[vvi++];
        }

        return mid_count+left_count+right_count;
    }
    
    int InversePairs(vector<int>& nums) {
        // write code here
        int length = nums.size();
        vv.resize(length);
        return fun(nums,0,length-1)%1000000007;
    }
};

因为要求时间复杂度为O(logn*n),所以简单的暴力匹配无法满足题解。

这里主要用到了归并排序的思想。

1.先将数据分为左右两个部分，然后递归求左部分的逆序数，求右部分的逆序数，最后求两个之间的逆序数。

2.主要问题出在求两个快之间的逆序数。

首先我们得明白一个知识，比如有两个快A,B。(这两个块间通过归并排序已经有序了)

A:4,6,7,8 B:2,5,9,10

我们依次从中取出元素进行排序。在A,B中第一个取的为2，那说明什么呢？

说明此时A中的所有元素都比2小，即A中的所有元素和2都可以构成一个逆序数。

因此让mid_count += mid-i+1。

然后再让其排序。

3.最后将三者的和返回即可。注意要用long int ，因为用例6的数据太大了。