剑指Offer51 数组中的逆序对

发表于 | 分类于 |
字数统计: 634 | 阅读时长 ≈ 3

链接

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

题意

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数

解法

考虑两种思路，一种办法是用分治
考虑归并排序，每次将数组划分成两部分，左半部分和右半部分都降序排列
然后用双指针分别指向两个部分的头部，在归并的过程中完成逆序对的计算
时间复杂度为O(nlogn)

另一种解法是离散化+树状数组
考虑序列[7,5,6,4]，用桶进行统计

1
2
index  ->  1 2 3 4 5 6 7 8 9
value  ->  0 0 0 1 1 1 1 0 0

可以看出，这一序列的第i-1位前缀和表示【有多少个数比i小】，因此从后往前遍历序列
每次记录当前位置的数所在的桶之前的前缀和，同时修改当前桶的数量
用树状数组完成这一更新和维护的过程，时间复杂度O(nlogn)

代码

分治做法

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
class Solution {
public:
    int ans = 0;
    void mergeCount(vector<int>& a, int s, int m, int e, vector<int>& b) {
        int p = s, q = m + 1;
        int index = s;
        while(p <= m && q <= e) {
            if (a[p] > a[q]) {
                b[index++] = a[p++];
                ans += (e - q + 1);
            }
            else {
                b[index++] = a[q++];
            }
        }

        while(p <= m) {
            b[index++] = a[p++];
        }

        while(q <= e) {
            b[index++] = a[q++];
        }
        for (int i = s; i <= e; i++) {
            a[i] = b[i];
        }

    }
    void mergeSort(vector<int>& a, int s, int e, vector<int>& b) {
        if (s < e) {
            int m = (s + e) / 2;
            mergeSort(a, s, m, b);
            mergeSort(a, m + 1, e, b);
            mergeCount(a, s, m, e, b);
        }
    }

    int reversePairs(vector<int>& nums) {
        vector<int> b(nums.size());
        mergeSort(nums, 0, nums.size() - 1, b);
        return ans;
    }
};

树状数组

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
class Solution {
public:
    int n;
    vector<int> bit;
    int sum(int i) {
        int s = 0;
        while(i > 0) {
            s += bit[i];
            // i -= i & -i;
            i = i & (i - 1);
        }
        return s;
    }
    void add(int i, int x) {
        while(i <= n) {
            bit[i] += x;
            i += i & -i;
        }
    }
    int reversePairs(vector<int>& nums) {
        n = nums.size();
        vector<int> res(nums);
        vector<int> a(n + 1);
        sort(res.begin(), res.end());
        bit.resize(n * 2);
        for (int i = 1; i <= n; i++) {
            a[i] = lower_bound(res.begin(), res.end(), nums[i - 1]) - res.begin() + 1;
        }
        int ans = 0;
        for (int i = n; i >= 1; i--) {
            ans += sum(a[i] - 1);
            add(a[i], 1);
        }
        return ans;
    }
};