算导学习——逆序对数量

  1. 1. 算导学习——逆序对数量

算导学习——逆序对数量

仅使用C++中类的部分性质,整体语言风格为C

需要前置知识:归并排序

符号A[1...n]指数组元素下标从1开始,到n结束,包括1和n

假设A[1..n]是一个有n个不同数的数组。若i<jA[i]>A[j],则对偶(i,j)称为A的一个逆序对(inversion)

求给定长度为n数组中逆序对的数量。要求最坏的情况需要\(\Theta(n lgn)\)时间

整体思想是通过分治,将问题规模不断缩小。这里,采用对归并排序进行一定的修改,从而解决此问题。

在归并排序中,每次将数组分为两个规模相同的部分。

如上图所示,假设左边的为数组A,右边的为数组B。

要求逆序对的数量,可分为以下三部分:

逆序对中的两个元素全在左边,全在右边,或一左一右

在同侧时,直接递归即可求解。故重点在异侧。

考虑归并排序时,左右两部分已经是有序的。分别设置指针ij,指向这两个数组A、B。而后按照归并排序的Merge方式移动这两个指针。

此时,若仅进行数组有序归并,则为一个归并排序。但为求逆序对数量,在其中增加一些步骤。

根据归并排序的性质,任意两个合并的数组一定是相邻的。即不失一般性,可取A[start...mid]B[mid+1...end]

且此时A、B均有序。

当A[i] > B[j]时,立即可得在A数组中i及之后的元素均大于B[j]。则逆序对的数量count += mid - i + 1。且获得所有以B[j]作为第二元的逆序对数量。如此循环至遍历完A、B数组。也就的到了所有的异侧逆序对。

考虑边界条件:

  • 当 i 至A的尾部,而 j 未至时,归并排序中的做法是复制B中剩余的值至数组剩余部分。假设此时j==kB[k…end]中任意元素大于A中所有元素。故不对count进行任何操作。
  • 当 j 至B的尾部,而 i 未至时,复制A中剩余的值至数组剩余部分。注意,以B[j]为逆序对第二元的逆序对数量已经在 j 到达B的尾部操作中完成。即B中已经没有元素能作为逆序对第二元。故不对count进行任何操作。

注意到,能够通过此方法增加逆序对数量而不失一般性的原因在于A、B是有序的,故在计算逆序数量的同时,必须保证递归“回退”过程中A、B始终有序。即对数组进行排序。

由于count的计算仅仅发生在A[i] > B[j]时,且为一赋值语句。故不影响整体时间复杂度。即整体时间复杂度与归并排序相同。为\(\Theta(n lgn)\)

以下附上完整代码:

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
class Inversion{

private:int count = 0;

public:int inversionCount(int* array, int n){
mergeSort(array, 0, n - 1);
return count;
}

private: void mergeSort(int* array, int first, int last){
if(first == last)
return;

int mid = (first + last) / 2;
mergeSort(array, first, mid);
mergeSort(array, mid+1, last);
merge(array, first, mid, last);
}

private: void merge(int* array, int first, int mid, int last){
int i = first, j = mid + 1, k = 0;
int temp[last - first + 1];
memset(temp, 0, last-first+1);

while (i <= mid && j <= last){
if(array[i] < array[j]){
temp[k] = array[i];
k++, i++;
}
if(array[i] > array[j]){
temp[k] = array[j];
k++, j++;
count += mid - i + 1;
}
}

while (i <= mid) temp[k++] = array[i++];
while (j <= last) temp[k++] = array[j++];

for (int l = 0; l < last - first + 1; ++l) {
array[l + first] = temp[l];
}
}
};