(剑指Offer)面试题36:数组中的逆序对

题目:

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

思路:

1、顺序扫描

顺序扫描整个数组,每扫描到一个数字,就将该数字跟后面的数字比较,如果大于的话,则这两个数字构成了逆序对。(比较简单,这里就不贴出代码)

时间复杂度:O(n^2)

2、归并思想

将数组不断地等分为两个子数组,然后自下而上地统计两个子数组各自的逆序对以及合并后的逆序对。

假设两个子数组左右分别为A,B,长度分为lenA,lenB,子数组已排好序,那么如何计算逆序对的个数呢?

当pA=lenA-1;pB=lenB-1;A[pA]>A[pB],说明A的最后一个数比B所有的数都大,此时个数为lenB,pA--;如果A[pA]<B[pB],说明左边的数不一定比右边的大,pB--;依次计算直至pA或pB为0,这样就得到了两个数组合并时的逆序对,再加上左子数组的逆序对和右子数组的逆序对,就等于整个数组的逆序对。

(代码中巧妙地利用了一个辅助数组来排序,参考下面的代码)

时间复杂度:O(nlogn)

代码:

#include <iostream>

using namespace std;

int InversePairsCore(int *data,int *copy,int start,int end){
if(start==end){
copy[start]=data[start];
return 0;
}
int length=(end-start)>>1;
int left=InversePairsCore(copy,data,start,start+length);
int right=InversePairsCore(copy,data,start+length+1,end); int i=start+length;
int j=end;
int copyIndex=end;
int count=0;
while(i>=start && j>=start+length+1){
if(data[i]>data[j]){
copy[copyIndex]=data[i];
copyIndex--;
i--;
count+=j-(start+length);
}
else{
copy[copyIndex]=data[j];
copyIndex--;
j--;
}
} for(;i>=start;i--)
copy[copyIndex--]=data[i];
for(;j>=start+length+1;j--)
copy[copyIndex--]=data[j]; return left+right+count;
} int InversePairs(int *data,int length){
if(data==NULL || length<=0)
return 0;
int* copy=new int[length];
for(int i=0;i<length;i++)
copy[i]=data[i];
int count=InversePairsCore(data,copy,0,length-1);
delete[] copy; return count;
} int main()
{
int A[]={7,5,6,4};
int length=sizeof(A)/sizeof(A[0]);
cout << InversePairs(A,length) << endl;
return 0;
}

在线测试OJ:

http://www.nowcoder.com/books/coding-interviews/96bd6684e04a44eb80e6a68efc0ec6c5?rp=2

AC代码:

class Solution {
public:
int InversePairs(vector<int> data) {
int length=data.size();
if(length<=1)
return 0;
int start=0;
int end=length-1;
int result=InversePairsCore(data,start,end);
return result;
} int InversePairsCore(vector<int> &data,int start,int end){
if(start>=end)
return 0;
int mid=start+((end-start)>>1);
int left=InversePairsCore(data,start,mid);
int right=InversePairsCore(data,mid+1,end); int i=start;
int j=mid+1;
int count=0;
vector<int> tmp;
while(i<=mid && j<=end){
if(data[i]>data[j]){
count+=end-j+1;
tmp.push_back(data[i]);
i++;
}
else{
tmp.push_back(data[j]);
j++;
}
} while(i<=mid)
tmp.push_back(data[i++]);
while(j<=end)
tmp.push_back(data[j++]); for(int k=start;k<=end;k++)
data[k]=tmp[k-start]; return left+count+right;
}
};
class Solution {
public:
int InversePairs(vector<int> data) {
int length=data.size();
if(length<=0)
return 0;
vector<int> copy(data.begin(),data.end());
int start=0;
int end=length-1;
int count=InversePairsCore(data,copy,start,end);
return count;
} int InversePairsCore(vector<int> &data,vector<int> &copy,int start,int end){
if(start==end){
copy[start]=data[start];
return 0;
}
int length=(end-start)>>1;
int left=InversePairsCore(copy,data,start,start+length);
int right=InversePairsCore(copy,data,start+length+1,end); int i=start+length;
int j=end;
int copyIndex=end;
int count=0;
while(i>=start && j>=start+length+1){
if(data[i]>data[j]){
copy[copyIndex--]=data[i--];
count+=j-(start+length);
}
else
copy[copyIndex--]=data[j--];
} for(;i>=start;i--)
copy[copyIndex--]=data[i];
for(;j>=start+length+1;j--)
copy[copyIndex--]=data[j]; return left+count+right;
}
};
上一篇:mysql查询时强制区分大小写


下一篇:把VueThink整合到已有ThinkPHP 5.0项目中