逆序对问题的求解 Solution of Inverse-Pairs Problem

发表于 Disqus：

时间复杂度最低的方法是，修改归并排序（Merge Sort），在排序同时对逆序对计数。时间复杂度为 \(O(n\log{n})\)。

代码：

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
class Solution {
    int inversePairsCore(int *data, int *copy, int first, int last) {
        if (first == last) {
            copy[first] = data[first];
            return 0;
        }
        int middle = (first + last)/2;
        int leftCount = inversePairsCore(copy, data, first, middle);
        int rightCount = inversePairsCore(copy, data, middle+1, last);
        
        int count = 0;
        int i = first, j = middle+1, k = first;
        // count # of inverse-pairs
        while (i <= middle && j <= last) {
            if (data[i] <= data[j]) { // ATTENTION!
                copy[k++] = data[i++];
                count += j - (middle+1);
            } else {
                copy[k++] = data[j++];
            }
        }
        while (i <= middle) {
            copy[k++] = data[i++];
            count += j - (middle+1);
        }
        while (j <= last) {
            copy[k++] = data[j++];
        }
        return leftCount + rightCount + count;
    }
public:
    int InversePairs(vector<int> data) {
        if (data.empty()) return 0;
        
        int *p = data.data(); // C++11
        int n = data.size();
        int *copy = new int[n];
        memcpy(copy, p, sizeof(int) * n);
        return inversePairsCore(p, copy, 0, n-1);
    }
};

注意：data[i] <= data[j] 这里不能写成<，因为在两个数相同的情况下，先选取左边的才能让总和尽可能小。比如 [1,2,1,2,1] 的逆序和是3，而不是7。

Ref.

  • 《剑指Offer》何海涛