您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

求最小的K個數：八種算法全景對比與C++實現

編輯：關於C

題目

輸入n個整數，找出最小的K個數。例：4,5,1,6,2,7,3,8 → 最小4個為1,2,3,4。

八種方法時間複雜度對比

方法	核心思想	時間復雜度	備註
1. 全排序	快排/歸併後取前K	O(n log n)	簡單通用
2. 選擇/交換排序	維護K個元素數組，每輪找最大	O(n K)	K小時尚可
3. 最大堆(容量K)	建堆O(K)，遍歷n-K元素，堆頂比較	O(n log K)	流式數據友好
4. BFPRT(中位數的中位數)	最壞O(n)選擇算法，取第K小為樞軸	O(n)	理論最優，常數大
5. Randomized-Select	隨機樞軸快選，期望O(n)	期望O(n)	工程常用
6. 計數/基數排序	線性排序，數值範圍小適用	O(n)	受數值範圍限制
7. 全量最小堆	全量建堆O(n)，彈出K次O(K log n)	O(n + K log n)	K接近n時優
8. 原地最小堆+限制下沉	建堆O(n)，彈出K次每次下沉≤K步	O(n + K^2)	特定場景優化

工程推薦選擇

通用場景：方法3（最大堆容量K），O(n log K)穩健，適合數據流。
單次查詢、K較小：方法5（隨機快選），期望線性，代碼簡短。
數據範圍小（如≤10^6）：方法6（計數排序），真正O(n)。
教學/面試：掌握方法1、3、5三大經典範式。

C++ STL一行式解法

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // 方法3：最大堆
    vector<int> getLeastNumbers_Heap(vector<int> nums, int k) {
        if (k <= 0 || nums.size() < k) return {};
        priority_queue<int> pq(nums.begin(), nums.begin()+k); // 最大堆
        for (size_t i=k; i= r) return;
            int i = l, j = r, pivot = nums[rand() % (r-l+1) + l];
            while (i <= j) {
                while (nums[i] < pivot) ++i;
                while (nums[j] > pivot) --j;
                if (i <= j) swap(nums[i++], nums[j--]);
            }
            if (k-1 <= j) quickSelect(l, j);
            else if (k-1 >= i) quickSelect(i, r);
        };
        quickSelect(0, nums.size()-1);
        return vector<int>(nums.begin(), nums.begin()+k);
    }
};

int main() {
    vector<int> a = {4,5,1,6,2,7,3,8};
    Solution sol;
    auto r1 = sol.getLeastNumbers_Heap(a, 4);
    auto r2 = sol.getLeastNumbers_QuickSelect(a, 4);
    for (int x : r1) cout << x << ' '; cout << endl;
    for (int x : r2) cout << x << ' '; cout << endl;
    return 0;
}