最小的K个数

  • 最大堆

    • 时间复杂度 O(n * logk)
    • 空间复杂度 O(k)
      1. class Solution {
      2. public:
      3. vector<int> smallestK(vector<int>& arr, int k) {
      4.    priority_queue<int, vector<int>, less<int>> que;
      5.    vector<int> res;
      6.    for (int n : arr) {
      7.        que.push(n);
      8.        if (que.size() > k) que.pop();
      9.    }
      10.    while (!que.empty()) {
      11.        res.push_back(que.top());
      12.        que.pop();
      13.    }
      14.    return res;
      15. }
      16. };

  • 快排变体

    • 不断进行划分
      • 如果pivot==k，左边的子数组就是最小的k个数
      • 如果pivot<k，继续划分右子数组
      • 如果pivot>k，继续划分左子数组
    • 时间复杂度 O(n)
      • 第一次 n
      • 第二次 n/2
      • 第三次 n/4
      • …
      • 相加 < 2n
        1. class Solution {
        2. public:
        3. vector<int> smallestK(vector<int>& arr, int k) {
        4. if (k <= 0) return {};
        5. if (arr.size() <= k) return arr;
        6. int l = 0, r = arr.size() -1;
        7. while (true) {
        8.     int pivot = partition(arr, l, r);
        9.     if (pivot == k) break;
        10.     else if (pivot < k) {
        11.         l = pivot + 1;
        12.     } else {
        13.         r = pivot - 1;
        14.     }
        15. }
        16. vector<int> res(arr.begin(), arr.begin()+k);
        17. return res;
        18. }
        19. int partition(vector<int> &arr, int l, int r) {
        20. int pivot = l;
        21. while (l != r) {
        22.     while (l < r && arr[r] > arr[pivot]) r--;
        23.     while (l < r && arr[l] <= arr[pivot]) l++;
        24.     if (l < r) swap(arr[r], arr[l]);
        25. }
        26. swap(arr[pivot], arr[l]);
        27. return l;
        28. }
        29. };