逆序对
发布于2021-01-19
上次编辑2021-04-20
Introduction
在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
即如果 \(i \lt j\) 且 \(A[i] \gt A[j]\)，\(A[i]\) 和 \(A[j]\) 构成一个逆序对。
如何计算数组中逆序对的总数？
算法
下面用 \(T(l,r)\) 表示子数组 \(A[l,r]\) 内的逆序对数量。
归并排序
将 \(A[l,r]\) 划分为 \(A[l,m]\) 和 \(A[m+1,r]\) 两部分。
如果我们已经得到了 \(T(l,m)\) 和 \(T(m+1,r)\) 的值，那么
\[T(l,r)=T(l,m)+T(m+1,r)+C\]
\(C\) 表示子数组 \(A[l,m]\) 和 \(A[m+1,r]\) 之间 形成的逆序对数量，即逆序对中的第一个数取自子数组 \(A[l,m]\)，第二个数取自子数组 \(A[m+1,r]\)。
如果要计算所有这样的逆序对，需要使用双重循环来遍历两个子数组的数，这样导致的时间复杂度为 \(\mathcal{O}(n^2)\)。
而如果两个子数组内的数据是有序的话，便可以在线性时间内得到结果。
| int count_inversions(vector<int> &A, int left, int mid, int right) {
// 计算有序数组 A[left, mid] 与 A[mid+1, right] 之间的逆序数
int cnt = 0;
for (int i = left, j = mid + 1; i <= mid; ++i) {
while (j <= right && A[i] > A[j]) ++j; // 如果 A[i] > A[j] 则 A[i+1,mid] 都大于 A[j]
cnt += j - (mid + 1);
}
return cnt;
}
|
所以要求解整个数组的逆序对数量，而且需要子数组是有序的，可以在 归并排序 的过程中增加上述步骤来实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | void merge(vector<int> &A, vector<int> &help, int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
while (i <= mid) {
if (j > right || A[i] <= A[j]) help[k++] = A[i++];
else help[k++] = A[j++];
}
while (j <= right) help[k++] = A[j++];
copy(help.begin() + left, help.begin() + right + 1, A.begin() + left);
}
void merge_sort(vector<int> &A, vector<int> &help, int left, int right) {
if (left >= right) return ;
int mid = left + ((right - left) >> 1);
merge_sort(A, help, left, mid), merge_sort(A, help, mid + 1, right);
merge(A, help, left, mid, right);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | void merge(vector<int> &A, vector<int> &help, int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
while (i <= mid) {
if (j > right || A[i] <= A[j]) help[k++] = A[i++];
else help[k++] = A[j++];
}
while (j <= right) help[k++] = A[j++];
copy(help.begin() + left, help.begin() + right + 1, A.begin() + left);
}
int merge_sort(vector<int> &A, vector<int> &help, int left, int right) {
if (left >= right) return 0;
int mid = left + ((right - left) >> 1);
int cnt = merge_sort(A, help, left, mid) + merge_sort(A, help, mid + 1, right);
cnt += count_inversions(A, left, mid, right);
merge(A, help, left, mid, right);
return cnt;
}
|
完整代码
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 | long long merge_sort(vector<int> &A, vector<int> &help, int left, int right) {
if (left >= right) {
return 0;
}
int mid = left + ((right - left) >> 1);
long long cnt = merge_sort(A, help, left, mid) + merge_sort(A, help, mid + 1, right);
// 计算逆序对数量
for (int i = left, j = mid + 1; i <= mid; ++i) {
while (j <= right && A[i] > A[j]) {
++j;
}
cnt += j - (mid + 1);
}
int i = left, j = mid + 1, k = left;
// 合并两个有序数组
while (i <= mid || j <= right) {
if (i <= mid && (j > right || A[i] <= A[j])) {
help[k++] = A[i++];
} else {
help[k++] = A[j++];
}
}
copy(help.begin() + left, help.begin() + right + 1, A.begin() + left);
return cnt;
}
|
二叉搜索树
树状数组
线段树
例题