您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

LeetCode Sort Colors 荷蘭國旗問題三路快排分區

編輯：C++ 入門

LeetCode Sort Colors 題目解析

給定包含 0、1、2 的數組，原地排序使相同顏色相鄰，順序為 0(紅)、1(白)、2(藍)。即荷蘭國旗問題。不可使用庫排序函數。

計數排序法 (兩遍掃描)

第一遍統計 0、1、2 的個數；第二遍按順序覆寫數組。時間 O(n)，空間 O(1)，需兩遍掃描。

class Solution {
public:
    void sortColors(int A[], int n) {
        int r = 0, w = 0, b = 0;
        for (int i = 0; i < n; i++) {
            if (A[i] == 0) r++;
            else if (A[i] == 1) w++;
            else b++;
        }
        for (int i = 0; i < n; i++) {
            A[i] = (i < r) ? 0 : (i < r + w ? 1 : 2);
        }
    }
};

單遍掃描三路分區法 (最優)

維護三個指針：p0 指向下一個 0 的位置，p2 指向下一個 2 的位置，curr 當前掃描位置。一遍掃描完成分區。

void sortColors(int A[], int n) {
    int p0 = 0, p2 = n - 1, curr = 0;
    while (curr <= p2) {
        if (A[curr] == 0) swap(A[curr++], A[p0++]);
        else if (A[curr] == 2) swap(A[curr], A[p2--]);
        else curr++;
    }
}