剑指 Offer 40. 最小的k个数 - 力扣（LeetCode） (leetcode-cn.com)

两种解法，一个利用最大堆，一个利用快速排序，都不难理解。

目录

利用堆

利用快速排序 

---

利用堆

代码：

#define top 0
#define NOP 0
class Solution {
    int k;
public:
    vector<int> getLeastNumbers(vector<int>& arr, int K) {
        k = K;
        vector<int> maxHeap(arr.begin(), arr.begin() + k);
        if (!k) return maxHeap;
        for (int pos = k / 2 - 1; pos != -1; --pos) sink(maxHeap, maxHeap[pos], pos);

        int size = arr.size();
        for (int i = k; i != size; ++i) {
            arr[i] < maxHeap[top] ? sink(maxHeap, arr[i], top) : NOP;
        }

        return maxHeap;
    }

    int sink(vector<int>& maxHeap, int pebble, int pos) {
        int bubble;
        while ((bubble = pos * 2 + 1) <= k - 1) {
            bubble != k - 1 && maxHeap[bubble + 1] > maxHeap[bubble] ? ++bubble : NOP;
            if (pebble >= maxHeap[bubble]) break;
            maxHeap[pos] = maxHeap[bubble];
            pos = bubble;
        }
        maxHeap[pos] = pebble;
        return 0;
    }
};

运行结果：

利用快速排序 

代码：

#define NOP 0
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (!k) return {};
        int front = 0, back = arr.size() - 1;
        int separatrix;
        while ((separatrix = partition(arr, front, back)) != k - 1) {
            separatrix > k - 1 ? back = separatrix - 1 : front = separatrix + 1;
        }
        vector<int> ans(arr.begin(), arr.begin() + k);
        return ans;
    }

    int partition(vector<int>& arr, int front, int back) {
        int pivot = arr[back];
        int j = front, i = j - 1;
        while (j != back) {
            arr[j] < pivot ? Fswap(arr[j], arr[++i]) : NOP;
            ++j;
        }
        arr[back] = arr[i + 1];
        arr[i + 1] = pivot;
        return i + 1;
    }

    int Fswap(int& a, int& b) {
        int temp = a;
        a = b;
        b = temp;
        return NOP;
    }
};

运行结果：