题目: 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
解法一:暴力法 统计数组中的逆序对的逆序对,可以使用暴力的方法,即顺序扫描整个数组,每扫描到一个数字的时候,逐个与该数字后面的数字比较大小,如果大于后面的某个数字,则形成一个逆序对。
暴力法简单易懂,容易实现,但是其时间复杂度为O(n2)O(n^2)。
解法二:归并统计 借鉴归并排序的思想,将数组拆分成单个有序的字数组,再进行合并的过程中进行逆序对的统计。时间复杂度为O(nlogn)O(nlogn)。归并排序的实现见:归并排序实现。
归并排序分为了2步骤; 第一步 数组拆分,直至规模较小的数组只含有一个元素; 第二步 合并两个已排好序的数组。
因此从整个数组拆分过程中,我们将它不断进行拆分,而拆分得到的两个数组,这样可以想到递归解决问题。
那么加入了逆序对后,如何考虑呢,实际上很简单。以从最下面的含一个元素的数组,到上层含多个元素的数组都有前后之分,这正好与逆序对性质相符,只要我们找出前面那一个数组中假设L[i] 大于后面一个数组中某个元素R[j],然后就知道前面那个数组在该元素L[i]之后的元素都应该是大于R[j]的。因为在归并过程我们也进行了排序。
参考代码:
#include <iostream>
using namespace std;
/*********************************
func:合并有序的相邻字数组,并统计逆序对数
para:a:左有序字数组;lenA:左有序字数组长度;b:右有序字数组;lenB:右有序字数组长度;inversePairsCount:相邻有序字数组a和b之间存在的逆序对数
return:void
*********************************/
void mergeAndCount(int* a,int lenA,int* b,int lenB,int& inversePairsCount){
int* temp=new int[lenA+lenB];
int index=0;
memset(temp,0,sizeof(int)*(lenA+lenB));
int* aPtr=a;
int* bPtr=b;
while(aPtr<a+lenA&&bPtr<b+lenB){
if(*aPtr<=*bPtr){
temp[index++]=*(aPtr++);
}
else{ //A大于B的元素,将B的元素与A的当前及后面的元素比较大小,判断逆序对数
for(int* aNow=aPtr;aNow<a+lenA;++aNow){
if(*aNow>*bPtr)
++inversePairsCount;
}
temp[index++]=*(bPtr++);
}
}
while(aPtr<a+lenA)
temp[index++]=*(aPtr++);
while(bPtr<b+lenB)
temp[index++]=*(bPtr++);
memcpy(a,temp,sizeof(int)*(lenA+lenB));
delete[] temp;
}
/*******************************************
func:统计给定数组A中存在逆序对数
para:A:待统计数组;len:数组A的长度;inversePairsCount:逆序对数
ret:void
*******************************************/
void inverseCount(int A[],int len,int& inversePairsCount){
int leftLen=len/2;
if(leftLen>0){
inverseCount(A,leftLen,inversePairsCount);
inverseCount(A+leftLen,len-leftLen,inversePairsCount);
mergeAndCount(A,leftLen,A+leftLen,len-leftLen,inversePairsCount);
}
}
int main(){
int A[]={7,5,6,4,1};
int inversePairsCount=0;
inverseCount(A,5,inversePairsCount);
cout<<"inversePairsCount:"<<inversePairsCount<<endl;
for(int i=0;i<5;++i)
cout<<A[i]<<" ";
getchar();
}
结果输出:
[1]剑指Offer.何海涛.电子工业出版社.