ROSALIND｜2-Way Partition (par)

發表於 更新於

重新排列一個整數數列，讓原數列的第一個數字成為新數列的分界點，滿足：左側數字 ≤ 該數字 < 右側數字。

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

Return: A permuted array $B[1..n]$ such that it is a permutation of $A$ and there is an index $1 \le q \le n$ such that $B[i] \le A[1]$ for all $1 \le i \le q-1$, $B[q] = A[1]$, and $B[i] > A[1]$ for all $q+1 \le i \le n$.

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

這題有一個直觀的解法。首先準備兩個空陣列，左側陣列存放小於等於基準值（即數列第一個數字）的數字，右側陣列存放大於基準值的數字。

執行算法時，由左至右逐一檢查數字。若當前的數字小於等於基準值，將其納入左側陣列，反之則納入右側陣列。持續這個步驟直到檢查完所有數字，再依序串聯左側陣列、基準值和右側陣列即完成排列。

1
2
3
4
5
6
7
8
def par(arr: list[int]) -> list[int]:
    L, R= [], []
    for i in range(1, len(arr)):
        if arr[i] <= arr[0]:
            L.append(arr[i])
        else:
            R.append(arr[i])
    return L + [arr[0]] + R

這個做法雖然需要額外空間暫存數字，但流程直觀而且保留了原數列的次序。若不在乎數字的順序，可以採用較為抽象，但能節省空間的指標方法。

指標法的核心在於用一個指標標記左右側的分界點，再用另一個指標紀錄當前檢查的位置。執行算法時，同樣由左至右檢查數字，比較其與基準值的大小。如果當前數字小於等於基準值，則將當前數字與位於分界線上的數字交換，再把分界線的位置向前更新一位。

這行為等同於透過更新分界線（而不是準備額外空間）創造分隔。分界線左側的數字皆小於等於基準值，右側的數字要不是尚未檢查就是大於基準值。因此，所有數字都檢查完畢後，再將基準值放到分界線左側變完成排列。

1
2
3
4
5
6
7
8
def par(arr: list[int]) -> list[int]:
    i = 1    # 分界點的位置
    for curr in range(1, len(arr)):
        if arr[curr] <= arr[0]:
            arr[i], arr[curr] = arr[curr], arr[i]
            i = i + 1
    arr[i-1], arr[0] = arr[0], arr[i-1] # 將基準值與分界點左邊的數字交換
    return arr

我覺得這算法還是要有圖解比較清楚。以數列 [4, 1, 5, 6, 7, 3] 為例，此數列的基準值為 4，分界線和當前位置都在數字數字 1。

1
2
3
4
5
  分界線/當前位置
    ↓
4   1   5   6   7   3
↑ 
基準值

因為數字 1 小於基準值，所以將其與分界線的數字交換（跟自己交換，所以位置不動），接著將分界線向右移動一單位距離，表示「小於等於區」多了一個數字。由於數字 5、6、7 皆大於基準值，所以接下來都沒有更新分界線，直到碰到數字 3 為止。

1
2
3
4
5
      分界線      當前位置
        ↓           ↓
4   1   5   6   7   3
↑ 
基準值

數字 3 小於基準值，所以將其與分界線的數字交換，並更新分界線的位置。

1
2
3
基準值      分界線  當前位置
↓           ↓       ↓
4   1   3   6   7   5

最後再把基準值與分界線左邊的數字交換，即完成數列劃分，結果為 [3, 1, 4, 6, 7, 5]

1
2
3
4
5
基準值      分界線  當前位置
↓           ↓       ↓
4   1   3   6   7   5
└───────┘
 交換數字