輸入 n 個整數，輸出其中最小的 k 個。例：[1,2,3,4,5,6,7,8], k=4 → [1,2,3,4]。
| 方案 | 思路 | 時間複雜度 | 空間複雜度 | 備註 |
|---|---|---|---|---|
| 1. 全量排序 | 快排 + 取前 k | O(n log n) | O(1) 或 O(log n) | 最簡單，過度計算 |
| 2. 選擇/插入維護 k 元素 | 維護大小 k 數組，每新元素與最大值比較 | O(n k) | O(k) | k 小時尚可 |
| 3. 最大堆（大小 k） | 建 k 最大堆，後續元素 < 堆頂則替換調整 | O(n log k) | O(k) | 工程常用，流式處理友好 |
| 4. 快速選擇 | Partition 劃分，遞歸處理目標側 | 平均 O(n)，最壞 O(n²) | O(1) | 原地操作，需隨機化 pivot |
| 5. BFPRT (中位數的中位數) | 嚴格 O(n) 最壞情況 | O(n) | O(1) | 理論優，工程常數大 |
| 6. 計數排序 | 數據範圍小時線性 | O(n + range) | O(range) | 受範圍限制 |
| 7. 最小堆（大小 n）+ 取 k 次 | 建 n 最小堆，彈出 k 次 | O(n + k log n) | O(n) | 空間換時間，k 很大時可考慮 |
| 8. 原地最小堆優化彈出 | 建堆後，每次彈出只下沉 k 次 | O(n + k²) | O(1) | 理論有爭議，實測接近方案 7 |
數學極限證明：當 k 為常數、n→∞ 時，O(n + k log n) < O(n log k)。但方案 7 需 O(n) 空間，方案 3 僅 O(k)。綜合考慮，方案 3（大小 k 最大堆）是工程首選：空間小、支持流式輸入、緩存友好。
#include <vector>
#include <queue>
#include <algorithm>
vector<int> findKSmallest(const vector<int> &nums, int k) {
if (k >= nums.size()) return nums;
if (k <= 0) return {};
// 大頂堆（預設 less<int> 即最大堆）
priority_queue<int> maxHeap(nums.begin(), nums.begin() + k);
for (size_t i = k; i < nums.size(); ++i) {
if (nums[i] < maxHeap.top()) {
maxHeap.pop();
maxHeap.push(nums[i]);
}
}
vector<int> result;
while (!maxHeap.empty()) {
result.push_back(maxHeap.top());
maxHeap.pop();
}
// 如需有序輸出，可 reverse 或 sort
return result;
}
int partition(vector<int> &a, int l, int r) {
int pivot = a[r], i = l - 1;
for (int j = l; j < r; ++j)
if (a[j] <= pivot) swap(a[++i], a[j]);
swap(a[i + 1], a[r]);
return i + 1;
}
void quickSelect(vector<int> &a, int l, int r, int k) {
if (l >= r) return;
int p = partition(a, l, r);
if (p == k) return;
else if (p > k) quickSelect(a, l, p - 1, k);
else quickSelect(a, p + 1, r, k);
}
// 調用：quickSelect(nums, 0, n-1, k-1); 前 k 個即為答案（無序）
「最小 k 個」是經典 Top-K 問題縮影。無銀彈，只有權衡：理解各算法的時間/空間/穩定性/流式支持特性，根據具體約束選擇，才是編程藝術的體現。
