劍指 Offer：最小的 K 個數（九度 OJ 1371）——快速選擇 + 部分排序

題目

輸入 n 個整數，找出最小的 k 個並按升序輸出。n, k ≤ 200,000，數值範圍 [0, 1e9]。

解法：QuickSelect 找第 k 小 + 對前 k 項快排

1. 用 Partition 將陣列分為 ≤ pivot 與 > pivot 兩部分
2. 若 pivot 索引 == k-1，前 k 項即為最小的 k 個（無序）
3. 否則遞迴處理左或右半部，平均 O(n)
4. 最後對前 k 項做完整快排 O(k log k)

核心程式碼

int partition(int l, int r) {
    int pivot = arr[r], i = l-1;
    for (int j=l; j k-1) r = idx-1;
        else l = idx+1;
        idx = partition(l, r);
    }
}
void qsort(int l, int r) { // 標準快排
    if (l >= r) return;
    int m = partition(l, r);
    qsort(l, m-1); qsort(m+1, r);
}

複雜度

• 時間：平均 O(n + k log k)，最壞 O(n²)（可用隨機 pivot 改善）
• 空間：O(1) 原地演算法

AC 記錄

Time: 950 ms, Memory: 1696 KB (C, 九度 OJ 1371)