本文为剑指 offer 系列第三十五篇。
在数组中寻找逆序对是归并排序的一个非常典型的应用。
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
解题思路
思路1
设置一个计数器，双层for循环，碰到逆序对则计数器+1，最后返回结果即可。
思路2
利用数据交换的排序方法来变相计算逆序对的数目。这里采用的是冒泡排序。
思路3
基于归并排序来进行计数。关于归并排序大家可以查具体的算法书的介绍。
这里我说一下为什么归并排序相比较于思路1和思路2要好的多。
我们知道归并排序首先是将数据进行分块，直到分到每个小块只有一个元素，然后将小块合并有序的大块。合并的时候采用有序链表合并的方法进行合并，针对于本问题而言，也就是在合并的时候进行逆序对的计算。
下面举例说明一下。比如我们合并的某一步骤，分别得到A = {3,5,6}和 B = {1,2,8}两个序列。
在合并的时候我们对两个数组进行从头的遍历进行合并，合并结果按照从小到大进行排列。
- 首先由于A中的3是要大于B中的1的，有序序列为{1},因为A中元素是升序的，A的第一个元素就大于1，所以A中所有的数据都是大于1的，从而仅仅是和1比较的时候就有3个逆序对，这样就可以直接通过A的前后索引计算出来，而不是一一比较再得到。
- 然后比较A中的3和B中的2.更新有序序列为{1,2}，此时针对于B可以得到逆序对有3个。
- 然后比较A中的3和B中的8.更新有序序列为{1,2,3},此时没有新的逆序对增加
- 然后比较A中的5和B中的8，更新有序序列为{1,2,3,5}，此时没有新的逆序对增加
- 然后比较A中的6和B中的8，更新有序序列为{1,2,3,5,6},此时没有新的逆序对增加
- 由于A已经遍历完成，将B中剩余元素添加到有序序列中即可。也就得到{1,2,3,5,6,8}。
- 最后得到上面两个序列的逆序对有6个。
对于其他的有序数组也采用类似的方式进行逆序对的计算。从而解决这个问题。
解题代码
思路1代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int InversePairs(vector<int> data) {
// 方法1 双层for循环
long res = 0;
for(int i = 0;i<data.size();i++){
for(int j = i+1;j<data.size();j++){
if(data[i]>data[j]) res++;
}
}
return res%1000000007;
}
};
|
时间复杂度为O(n^2),空间复杂度为O(1)
思路2代码
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
| class Solution {
public:
int InversePairs(vector<int> data) {
//方法2: 冒泡排序 O(n^2) 通过率为50%
if(data.size() == 0) return 0;
return helperByBubbleSort(data);
}
// 方法2的辅助函数
int helperByBubbleSort(vector<int> data){
long res = 0;
bool notfinish = true;
int len = data.size();
for(int i = 0; i < len-1 && notfinish; i++){
notfinish = false;
for(int j = 0; j < len-i-1; j++){
if(data[j] > data[j+1]){
swap(data[j],data[j+1]);
notfinish = true;
res++;
}
}
}
return res%1000000007;
}
};
|
时间复杂度最坏的情况为O(n^2),最好的情况为O(n),空间复杂度为O(1)
思路3代码
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
| class Solution {
public:
int InversePairs(vector<int> data) {
//方法3: 归并排序
if(data.size() == 0) return 0;
return helperByMergeSort(data,0,data.size()-1)%1000000007;
}
// 方法3的辅助函数
int helperByMergeSort(vector<int>& data,int start,int end){
if(start == end) return 0;
int mid = start+((end-start)>>1);
int left = helperByMergeSort(data,start,mid);
int right = helperByMergeSort(data,mid+1,end);
vector<int> temp(end-start+1,0);
int i = start, j = mid+1, count = 0, index = 0;
while(i <= mid && j<=end){
if(data[i] > data[j]){
count = (count + mid - i + 1)%1000000007;
temp[index++] = data[j++];
}else{
temp[index++]= data[i++];
}
}
// 如果存在一部分没有取完
while(i<=mid){
temp[index++] = data[i++];
}
while(j<=end){
temp[index++] = data[j++];
}
//把排好序的结果放回原数组中
for(int i = start; i<= end; i++){
data[i] = temp[i-start];
}
return (count+left+right)%1000000007;
}
};
|
时间复杂度O(nlogn),空间复杂度为O(n)
参考
1.剑指Offer-37-数组中逆序对
2. 剑指Offer（三十五）：数组中的逆序对
以上，本题结束！