算法疑难杂症

分治-逆序对个数

字数统计: 1.2k字   |   阅读时长: 4分

摘要: 分治法解逆序对个数问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 分治 中，我们详细总结了分治法的内容，分治法有一个重要应用是归并排序。关于归并排序的算法细节和代码模板，可以参考这篇文章: 数组排序。

一般写排序不会写归并排序，但是很多分治算法都基于归并排序的思想：分的阶段进行排序，合的阶段做归并同时借助有序的特性更高效地统计目标信息。

这种思想最经典的问题是逆序对的个数。本文我们就来看一下逆序对的问题。

逆序对问题在 leetcode 上有一个变种翻转对问题，此前写过题解，参考: 翻转对题解。

逆序对问题

在这个问题中，您必须分析特定的排序算法——超快速排序。

该算法通过交换两个相邻的序列元素来处理 n 个不同整数的序列，直到序列按升序排序。

对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
输入格式
输入包括一些测试用例。
每个测试用例的第一行输入整数 n，代表该用例中输入序列的长度。
接下来 n 行每行输入一个整数 ai,代表用例中输入序列的具体数据，第 i 行的数据代表序列中第 i 个数。
当输入用例中包含的输入序列长度为 0 时，输入终止，该序列无需处理。

输出格式
对于每个需要处理的输入序列，输出一个整数 op，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。

数据范围
0<=n<500000,
一个测试点中，所有 n 的和不超过 500000。
0<=ai<=999999999

输入样例：
5
9
1
0
5
4
3
1
2
3
0
输出样例：
6
0

题解

算法: 分治

我们首先写出分治法的框架：

1
2
3
4
5
6
7
8
分解: 将原序列 x=a[l..r] 分为 x1=a[l, (l+r)/2], x2=a[(l+r)/2 + 1, r] 两部分

解决: 如果原序列 x 的长度为 1，则直接返回此序列和 0 即可

合并: 左边部分的逆序对个数为 n1, 排序后的序列 y1
      右边部分的逆序对个数为 n2, 排序后的序列 y2
      对 y1, y2 做 2 路归并，归并后的序列为 y，并顺便统计逆序对个数 n3
      返回 y 和 n1 + n2 + n3

这里的一个问题就是在二路归并的时候如何顺便统计逆序对个数。

我们考察合并阶段在进行二路归并过程，如下图：

当前 y1 序列进行到 i，y2 序列进行到 j。此时问: y1 中有多少比 y2[j] 大，并将其添加到对 n3 的贡献中。

由于 y1[0..i-1], y2[0..j-1] 已经进入 tmp，并且小于等于 y1[i], y2[j]，因此 y1[0..i-1] 中是不会对 n3 有贡献的。

所以就要看 y1[i..m1-1] 中有多少大于 y2[j]，根据 y1[i] 与 y2[j] 的大小关系分类讨论。

  • 如果 y1[i] > y2[j]，则按二路归并的流程将 y2[j] 压进 tmp，并对 n3 贡献 m1 - i。
  • 如果 y1[i] <= y2[j]，则按二路归并的流程将 y1[i] 压进 tmp，此时 y2[j] 对 n3 的贡献还不确定。

代码 (C++)

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
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

ll merge_sort(vector<ll>& a, int l, int r)
{
    // 解决
    if(l == r)
        return 0;
    // 分解
    int mid = (l + r) / 2;
    ll n1 = merge_sort(a, l, mid);
    ll n2 = merge_sort(a, mid + 1, r);
    // 合并
    int i = l;
    int j = mid + 1;
    ll n3 = 0;
    vector<int> tmp(r - l + 1);
    int k = 0;
    while(i <= mid && j <= r)
    {
        if(a[i] > a[j])
        {
            n3 += mid + 1 - i;
            tmp[k++] = a[j++];
        }
        else
            tmp[k++] = a[i++];
    }
    while(i <= mid)
        tmp[k++] = a[i++];
    while(j <= r)
        tmp[k++] = a[j++];
    for(int i = l; i <= r; ++i)
        a[i] = tmp[i - l];
    return n1 + n2 + n3;
}

int main()
{
    vector<ll> a;
    while(true)
    {
        int n;
        cin >> n;
        if(n == 0)
            break;
        a.assign(n, -1);
        for(int i = 0; i < n; ++i)
            cin >> a[i];
        ll ans = merge_sort(a, 0, n - 1);
        cout << ans << endl;
    }
}
Share