ROSALIND｜Counting Inversions (INV)

發表於

給定一個數列，求其反序數對 (inversions) 的數量。

Given: A positive integer $n \leq 10^5$ and an array $A[1..n]$ of integers from $-10^5$ to $10^5$.

Return: The number of inversions in $A$.

(https://rosalind.info/problems/inv/)

在遞增數列裡，如果前面的數字比後面的數字大，這兩個數字就構成一個反序數對 (inversions)。例如數列 [3, 2, 1] 便有 [3, 2]、[2, 1] 和 [3, 1]，共三個反序數對。

反序數對的數量可以在 merge sort 的過程中順帶得出。在合併兩個已排序的數列時，如果左側數列的最小數字小於右側數列的最小數字，表示兩者順序正常可直接合併。

如果左側數列的最小數字大於右側數列的最小數字，這兩個數字就構成一個反序數對。不僅如此，因為左側數列已經排序，所以我們可以得知剩餘的其他數字都比這個右側數字還大。

舉例來說，合併 [3, 4, 5] 和[1, 2]的時候，比較 3 > 1，因為左側數列已排序，所以剩餘的 [4, 5] 也會比 1 大。換句話說，反序數對的數量等於左側數列的剩餘長度，亦即 len(left) - i。

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
def merge(left, right):
    i, j = 0, 0
    # 新增一個變項紀錄反序數對的數量
    inv = 0
    out = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:   
            out.append(left[i])
            i = i + 1
        else:
            # 左側數字大於右側數字時構成反序
            out.append(right[j])
            j = j + 1
            # 因為左側數列剩餘的數字都比右側數字大
            # 所以反序數對的數量等於左側數列的剩餘數字數量
            inv = inv + len(left) - i
    out.extend(left[i:])
    out.extend(right[j:])
    return out, inv
def inv(l):
    if len(l) <= 1:
        return l, 0
    mid = len(l) // 2
    left, left_inv = inv(l[:mid])
    right, right_inv = inv(l[mid:])
    # 計算合併時新生成的反序數對
    merged, merge_inv = merge(left, right)
    # 反序數對的總數 = 左側 + 右側 + 合併
    return merged, left_inv + right_inv + merge_inv