SOTSOG学习笔记记录
Posts Notes Algorithms Awesome Tags Categories
SOTSOG学习笔记记录

逆序对

介绍

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。即如果 $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)$。

而如果两个子数组内的数据是有序的话，便可以在线性时间内得到结果。

1
2
3
4
5
6
7
8
9

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;
}

二叉搜索树

树状数组

线段树

例题

参考