题目链接

https://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5

题意

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。题目保证输入的数组中没有的相同的数字。

解题思路

在归并排序的过程中计逆序对。时间复杂度O(nlogn),空间复杂度O(n)。

• 将数组从中间分成前后两个数组(递归到只有一个数据项)。注意数组都是含该数组首尾坐标元素的。
• 然后合并并排序两个数组，排序结果在copy数组。具体地，i、j指针从两个数组后向前遍历，将大的拷贝到copy数组(copy数组从后往前填)。最后剩下的数组的剩下的部分一并拷贝到copy数组
• 在合并过程中计逆序对，若i指向的元素大于j，则count+=j-mid;即mid+1到j的元素都比i指向的元素小。
• 最终返回的count是两个数组内部的逆序对 + 合并过程中的逆序对数（即上一条）。

注意

• 每次递归传参copy和array换位置(滚动数组)。保证(左右子数组返回后)开始时data[l,mid]和data[mid+1,r]内部有序，结束时copy[l,r]内部有序。
• size_t 是>=0 所以当i=0，i--，i会等于一个较大正数而不是-1，仍满足while(i>=l)，使得程序错误。
• cnt+=(j-mid)%1000000007应改为cnt=(cnt+(j-mid))%1000000007

代码

class Solution {

public:

    int InversePairs(vector<int> data) {

        int cnt=0;

        if(!data.empty()){

            vector<int> copy;

            for(auto it=data.begin();it!=data.end();++it){

                copy.push_back(*it);

            }

            cnt=inversePairCnt(data,copy,0,data.size()-1);

        }

        return cnt;

    }

private:

    int inversePairCnt(vector<int>& data,vector<int>& copy,int l,int r){

        if(l==r){

            return 0;

        }

        int mid=(l+r)>>1;

        int leftCnt=inversePairCnt(copy,data,l,mid);

        int rightCnt=inversePairCnt(copy,data,mid+1,r);

        //开始：此时data[l,mid]和data[mid+1,r]内部有序，copy[l,mid]和copy[mid+1,r]内部无序

        int i=mid;

        int j=r;

        int copyIndex=r;

        int cnt=0;

        while(i>=l&&j>mid){

            if(data[j]>data[i]){

                copy[copyIndex--]=data[j--];

            }

            else{

                cnt=(cnt+(j-mid))%1000000007;//

                copy[copyIndex--]=data[i--];

            }

        }

        while(i>=l){//

            copy[copyIndex--]=data[i--];

        }

        while(j>mid){

            copy[copyIndex--]=data[j--];

        }

        //结束：此时copy[l,r]内部有序,data[l,r]内部无序

        return (leftCnt+rightCnt+cnt)%1000000007;

    }

};