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

#include <algorithm>
#include <random>
#include <vector>
class Solution {
public:
    long int countMerge(vector<int>& data,vector<int>& assist,int start,int end,int mid)
    {
	   //如果当前只有一个元素，逆序数记为0（递归出口）
        if(start>=end)
        {
            return 0;
        }
        else
        {
            //递归
            int midl=start+(mid-start)/2;//左边区域的逆序数
            long int leftcount=countMerge(data,assist,start,mid,midl);


            int midr=mid+1+(end-mid-1)/2;//右边区域的逆序数
            long int rightcount=countMerge(data,assist,mid+1,end,midr);



            //计算两个区域合并在一起的逆序数
            int i=start,j=mid+1;
            int tempcount=0;
            while(i<=mid)
            {
                if(data[j]<data[i]&&j<=end)
                {
                    ++tempcount;
                    ++j;
                    continue;
                }    
                leftcount+=tempcount;
                ++i;
            }



            //归并
            i=start,j=mid+1;
            int start2=start;
            while(i<=mid&&j<=end)
            {
                if(data[i]<data[j])
                {
                    assist[start2++]=data[i];
                    ++i;
                }
                else 
                {
                    assist[start2++]=data[j];
                    ++j;
                }
            }

            while(j<=end)
            {
                assist[start2++]=data[j];
                ++j;
            }
            while(i<=mid)
            {
                assist[start2++]=data[i];
                ++i;
            }
		  
            while(start<start2)//注意这里是小于，start2多向后移动了一位
            {
                data[start]=assist[start];
                ++start;
            }


			//返回逆序数
            return leftcount+rightcount;

        }



    }
    int InversePairs(vector<int> data) 
    {
        vector<int> assist;
        assist.resize(data.size()+1);//注意一定要resize()否则会溢出错误
        long int res=countMerge(data,assist,0,data.size()-1,(data.size()-1)/2);
        return res%1000000007;
    }
};

给定数组data,如果从中间分为左右两部分，如果左边逆序数为n, 右边逆序数为m,那么总逆序数为n+m+x;x为左边元素与右边元素组成逆序对的逆序数（一个序列总可以经过多次划分，分为左边或者右边元素个数为1，此时n/m为0,因此只要能计算x，就能设计递归解决这个题）。

不难发现，x的值与左右两边内部排序没有关系。如果左右两边都是升序列，那么可以在O(n)时间范围内求出x(这是因为计算左边每个元素逆序数时，右边不用回溯）。

根据以上描述，此题实际上是归并排序，只不过多加了一个计算x,归并有序序列的时间复杂度也是O(n)，因此总复杂仍为O(nlogn)。