面试题36:数组中的逆序对

题目:在数组中的两个数字如果前面一个大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中所有逆序对的总数。


分析

如果采用简单粗暴的方法,即遍历数组,对每个数,检查后面的每一个数是否小于它。时间复杂度为O(n2)。

实际上我们可以采用归并排序来解决这个问题,只需要在归并每一个数字时,通过计算而不是遍历的方式得到后面有多少个元素小于它(常数时间)。这样总的时间复杂度就是归并排序的时间复杂度为O(nlgn),不并且需要额外的O(n)的空间。这又是一个“以空间换时间”的做法。

而具体的计算方法如下:归并时从后往前归并,如果前面的数大于后面的,说明他们是有序的,不构成逆序对;否则说明前面的数大于后面的数字,并且可以推断出前面的数大于后面中该数字之前的所有数字。例子如下:

1,4,5,7
2,3,6,8

所以以上1,4,5,7,2,3,6,8数组中共有7组逆序对。

代码如下:

{
    int i=mid,j=right,k=right;
    while(i>=left && j>mid)
    {
        if(v[i]<v[j])
            tmp[k--]=v[j--];
        else
        {
            tmp[k--]=v[i--];
            count+=(j-mid);
        }
    }
    while(i>=left)
        tmp[k--]=v[i--];
    while(j>mid)
        tmp[k--]=v[j--];
    for(i=left;i<=right;++i)
    {
        v[i]=tmp[i];
    }
}

void MergeSort(vector<int>&amp; v,int left,int right,vector<int>&amp; tmp,int&amp; count)
{
    if(right-left>1)
    {
        int mid=left+(right-left)/2;
        MergeSort(v,left,mid,tmp,count);
        MergeSort(v,mid+1,right,tmp,count);
        Merge(v,left,mid,right,tmp,count);
    }
    else
    {
        Merge(v,left,left,right,tmp,count);
    }
}

int InversePairs(vector<int> v)
{
    int count=0;
    vector<int> tmp;
    tmp.resize(v.size());
    MergeSort(v,0,v.size()-1,tmp,count);
    return count;
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")