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

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


分析

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

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

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

<center>1,4,5,7</center> 和<center>2,3,6,8</center>

  • 首先,7<8,此时临时数组中后半部分的数字为8,count加0。
  • 然后7和6,7>6,构成逆序对,并且6之前的所有元素均和7构成逆序对,count加3。临时数组中值为7,8。
  • 5<6,不构成逆序对,count加0.临时数组中后半部分值为6,7,8。
  • 5>3,所以5和2,3都构成逆序对,count加2.临时数组中值为5,6,7,8。
  • 4>3,所以4和2,3都构成逆序对,count加2,临时数组中值为4,5,6,7,8。
  • 接下来两步,1<2和3,不构成逆序对,直接放入临时数组即可,值为1,2,3,4,5,6,7,8。

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

代码如下:

Merge(vector<int>& v,int left,int mid,int right,vector<int>& tmp,int& count)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
{
int i=mid,j=right,k=right;
while(i&gt;=left &amp;&amp; j&gt;mid)
{
if(v[i]&lt;v[j])
tmp[k--]=v[j--];
else
{
tmp[k--]=v[i--];
count+=(j-mid);
}
}
while(i&gt;=left)
tmp[k--]=v[i--];
while(j&gt;mid)
tmp[k--]=v[j--];
for(i=left;i&lt;=right;++i)
{
v[i]=tmp[i];
}
}
void MergeSort(vector&lt;int&gt;&amp; v,int left,int right,vector&lt;int&gt;&amp; tmp,int&amp; count)
{
if(right-left&gt;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&lt;int&gt; v)
{
int count=0;
vector&lt;int&gt; tmp;
tmp.resize(v.size());
MergeSort(v,0,v.size()-1,tmp,count);
return count;
}

以上

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

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

<div>来自为知笔记(Wiz)</div>