JZ35 数组中的逆序对

本文最后更新于：2022年4月9日 中午

image-20211008105618377

Solution

  • 分治法，借助归并思想
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
class Solution {
public:
    int InversePairs(vector<int> data) {
        if (data.size() == 0) return 0;
        vector<int> tmp(data);  // 辅助数组，用于保存排序结果
        int res = mergeSort(data, tmp, 0, data.size()-1);    // 注意参数顺序
        return res;
    }
private:

    int mergeSort(vector<int>& data, vector<int>& tmp, int l, int r) {
        if (l >= r) return 0;
        int mid = l + (r - l) / 2;
        
        // !注意数据交换
        int left = mergeSort(tmp, data, l, mid);    // 注意参数顺序
        int right = mergeSort(tmp, data, mid+1, r);    // 注意参数顺序
        
        // 合并阶段
        int res = 0, tmpIdx = l;
        int low1 = l, high1 = mid, low2 = mid+1, high2 = r;
        
        while (low1 <= high1 && low2 <= high2) {
            if (data[low1] < data[low2]) {
                tmp[tmpIdx++] = data[low1++];
            } else {
                // 计算逆序对
                tmp[tmpIdx++] = data[low2++];
                res += high1 - low1 + 1;
                res %= 1000000007;
            }
        }
        while (low1 <= high1) {
            tmp[tmpIdx++] = data[low1++];
        }
        while (low2 <= high2) {
            tmp[tmpIdx++] = data[low2++];
        }
        
        return (left + right + res) % 1000000007;
    }
};