逆序数介绍(—)

参考内容

逆序数的求法


拖更大王终于更新了一篇博客=-=

最近遇到了几个逆序数的问题,感觉是一类的,总结一下。
首先,逆序数的定义:

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

举个例子:165324这个排列中,65, 63, 62, 64, 53, 52, 54, 32为逆序,该排列的逆序数为7,是奇排列。

所谓逆序,无非就是与标准排序相反的序列。计算逆序数,可以按照这样的思路来算:
比如对于54321这样一个序列:

(1)对于5,他在第一位,不会跟前面的任何一个数字构成逆序。

(2)对于4,他在第二位,前面有数字5会跟他构成逆序,此处+1

(3)对于3,他在第三位,前面有数字54会跟他构成逆序,此处+2

最后可得,逆序数为1+2+3+4=10

上面是汇总了对于每个位置的元素,其前面位置比其大的元素总数的和。
当然,也可以来计算每个位置元素,其后面位置比其小的元素总数的和。道理是一样的。

逆序数有三类问题,分别是:

(1)给出一个排列,求出该排列逆序数是多少

(2)给出逆序数,求排列数

(3)根据每个数的逆序数,求原排列

本文解决最简单的第一个问题.

解决这个问题有三种做法。

方法一

首先,最无脑的,当然是对于每个数字a[i],分别与它前面的数字a[j] (j < i)进行比较。如果a[j] > a[i],则逆序数加一。本算法的时间复杂度为O(N ^ 2)。
(隐约感觉与最坏情况下的插入排序有点像==)

代码
(测试平台为SJTUOJ,当然一定会超时了…)

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
#include <bits/stdc++.h>
using namespace std;
//core
int calInversions(vector<int>& nums)
{
int result = 0;
for(int i = 1; i < nums.size(); ++i)
for(int j = 0; j < i; ++j)
if(nums[j] > nums[i])
result++;
return result;
}
//OJ接口
int main() {
int num;
cin >> num;
vector<int> nums;
while(num--)
{
int tmp;
cin >> tmp;
nums.push_back(tmp);
}
cout << calInversions(nums);
return 0;
}

方法二

利用MergeSort来处理这个问题。计数的过程发生在Merge的过程中。在merge的时候,如果左边的元素a[i]比右边的元素b[j]大,说明左边集合中,a[i]右侧的元素都比b[j]大。这时候逆序数应该加上len1-i+1(包括a[i])。整个过程与MergeSort相差无几,所以时间复杂度为O(NlogN)。

代码

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
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
//core
long sum = 0;
void merge(vector<int>& nums, int startIndex, int midIndex, int endIndex) {
vector<int> tmp;
int i = startIndex;
int j = midIndex + 1;
while(i <= midIndex && j <= endIndex) {
if (nums[i] <= nums[j]) {
tmp.push_back(nums[i++]);
} else {
tmp.push_back(nums[j++]);
sum += (midIndex - i + 1);
}
}
while (i <= midIndex) {
tmp.push_back(nums[i++]);
}
while( j <= endIndex) {
tmp.push_back(nums[j++]);
}
for (int curr = 0; curr < tmp.size(); curr++) {
nums[curr + startIndex] = tmp[curr];
}
}
void mergeSort(vector<int>& nums, int startIndex, int endIndex) {
if (startIndex == endIndex) {
return;
}
int midIndex = (startIndex + endIndex) / 2;
mergeSort(nums, startIndex, midIndex);
mergeSort(nums, midIndex + 1, endIndex);
merge(nums, startIndex, midIndex, endIndex);
}
//OJ接口
int main() {
int num;
cin >> num;
vector<int> nums;
while(num--) {
int tmp;
cin >> tmp;
nums.push_back(tmp);
}
mergeSort(nums, 0, nums.size() - 1);
cout << sum;
return 0;
}

方法三

还可以用树状数组来解决这个问题。此处先留个坑,日后来填。

文章目录
  1. 1. 方法一
  2. 2. 方法二
  3. 3. 方法三
|