逆序对

发表于 更新于 本文字数： 968 阅读时长 ≈ 4 分钟

逆序对计算

1 归并排序

归并排序天然就可统计逆序对，在归并时有以下两种方式统计：

当左侧当前指针指向位置的数字CUR较小时，本轮将其加入归并后的数组，注意到右数组当前指针左边的都是小于CUR的，但是他们位置却在其右侧，所以逆序对贡献为l2-old_l2

1
2
3
4
5
6
if (a <= b) { // 这里包含等于 可以用全1数组模拟想想
    trr[p++] = arr[l1++];
    ret += (l2-old_l2);
}
else 
    trr[p++] = arr[l2++];

当右侧当前指针指向位置的数字CUR较小时，本轮将其加入归并后的数组，注意到左数组当前指针及其右边都是大于CUR的，但是他们的位置却在其左侧，所以逆序对的贡献为old_l2 - l1

1
2
3
4
5
6
if (a <= b)  // 这里包含等于 可以用全1数组模拟想想
    trr[p++] = arr[l1++];
else {
    trr[p++] = arr[l2++];
    ret += (old_l2 - l1);
}

下面是完整代码

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
class Solution {
public:
    int ret = 0;
    void merge(vector<int>& arr, vector<int>& trr, int l1, int r1, int l2, int r2) {
        int l = l1, r = r2;
        int p = l1, old_l2 = l2;
        while (l1 <= r1 || l2 <= r2) {
            long long a = l1 <= r1 ? arr[l1] : LLONG_MAX;
            long long b = l2 <= r2 ? arr[l2] : LLONG_MAX;
            if (a <= b) { // !!!!! <= 等于时也必须，不然右侧添加一堆等于的，再计算，结果肯定大了呀
                trr[p++] = arr[l1++];
                ret += (l2-old_l2); // 只需要在这里加上这句，收集逆序对
            }
            else 
                trr[p++] = arr[l2++];
        }
        for (int i = l; i <= r; ++i)
            arr[i] = trr[i];
    }
    void core(vector<int>& arr, vector<int>& trr, int l, int r) {
        if (l >= r) return;
        int m = (l + r) / 2;
        core(arr, trr, l, m);
        core(arr, trr, m + 1, r);
        merge(arr, trr, l, m, m + 1, r);
    }
    int reversePairs(vector<int>& nums) {
        vector<int> trr(nums.size());
        core(nums, trr, 0, (int)nums.size() - 1);
        return ret;
    }
};

2 离散化+树状数组

树状数组可以非常方便进行区间统计和单点修改，对于原数组，我们从后往前遍历，依次将其加入树状数组（计数），并求其左侧（小于的）之前的所有已插入的数字的和，最终即可求得总的逆序对。然而，原数组的数值范围波动较大，不能直接用树状数组去记录，其间必有许多0表现出极大的稀疏性，因此需要对原数组进行离散化。所谓离散化，即将原数组映射到1~N的数据范围，让数据的范围全部聚集在一起，减少空间浪费，有利于树状数组发挥。因为在该问题中我们不关心数据的绝对大小，仅关心数据的相对大小，所以可以离散化。离散化需要借助偏向的二分查找进行。

对于数组[1,3,2,4,1]，离散化后的结果是1,4,3,5,1，程序处理过程中树状数组的变化为（树状数组0位弃用）：

1
2
3
4
5
6
7
8
9
对于原数组 [1,4,3,5,1]
从后往前遍历 1->5->3->4->1
X    [0,0,0,0,0,0]   ret = 0 初始
1    [0,1,1,0,1,0]   ret = 0
5    [0,1,1,0,1,1]   ret = 1
3    [0,1,1,1,2,1]   ret = 2
4    [0,1,1,1,3,1]   ret = 4
1    [0,2,2,1,4,1]   ret = 4
最终逆序对即为4
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
// 树状数组
class Trr {
    vector<int> trr;
public:
    static int lowbit(int a) { return a & -a; }
    Trr(const vector<int>& arr) : trr(arr.size() + 1) {
        for (int i = 0; i < arr.size(); ++i) {
            int t = i + 1;
            while (t < trr.size()) {
                trr[t] += arr[i];
                t += lowbit(t);
            }
        }
    }

    int query(int n) { // from 1
        int ret = 0;
        while (n) {
            ret += trr[n];
            n -= lowbit(n);
        }
        return ret;
    }

    void update(int pos, int diff) { // from 1
        while (pos < trr.size()) {
            trr[pos] += diff;
            pos += lowbit(pos);
        }
    }
};

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        // 离散化(nlogn)
        vector<int> tmp(nums);
        sort(tmp.begin(), tmp.end());
        for (auto& e : nums)
            e = lower_bound(tmp.begin(), tmp.end(), e) - tmp.begin() + 1;
        // 树状数组统计逆序对(nlogn)
        Trr trr(vector<int>(nums.size())); // 初始化全0
        int ret = 0;
        for (int i = nums.size() - 1; i >= 0; --i) {
            trr.update(nums[i], 1);
            ret += trr.query(nums[i] - 1);
        }
        return ret;
    }
};

小记

  • 已知的树状数组的两种用途
    • 原数组的下标作为索引，进行区间统计和修改
    • 原数组的值作为下标，进行区间计数（本题）