## 求最小的k个数 题目：输入一个n个整数，找出其中最小的k个数。例如输入4，5，1，6，2，7，3，8这8个数字，则最小的4个数字是1, 2, 3, 4。 ### 解法1 利用快排partion的思路，将最小的k个数放在前面，实现如下： ```cpp /** * 小于等于pivot放在前面 */ int partition(vector<int>& nums, int left, int right) { int pivot = nums[right]; int index = left; for (int i = left; i < right; ++i) { if (nums[i] <= pivot) { swap(nums[i], nums[index++]); } } swap(nums[index], nums[right]); return index; } vector<int> minTopK(vector<int>& nums, int k) { int left = 0; int right = nums.size() - 1; int index = partition(nums, left, right); while (index + 1 != k) { if (index + 1 > k) { right = index - 1; } else { left = index + 1; } index = partition(nums, left, right); } vector<int> result; for (int i = 0; i < k; ++i) { result.push_back(nums[i]); } return result; } ``` ### 解法2 利用最大堆 ```cpp class MaxHeap { public: MaxHeap(size_t capacity) : capacity_(capacity), count_(0) {} void put(int x) { if (count_ < capacity_) { datas_.push_back(x); shiftUp(count_++); } else { if (x < datas_[0]) { datas_[0] = x; shiftDown(0); } } } vector<int> getDatas() { return datas_; } private: void shiftUp(int k) { while (k > 0) { int parent = (k - 1) / 2; if (datas_[k] <= datas_[parent]) break; swap(datas_[k], datas_[parent]); k = parent; } } void shiftDown(int k) { while (2 * k + 1 < count_) { int max = 2 * k + 1; if (max + 1 < count_ && datas_[max + 1] > datas_[max]) max++; if (datas_[max] <= datas_[k]) break; swap(datas_[k], datas_[max]); k = max; } } private: size_t count_; size_t capacity_; vector<int> datas_; }; vector<int> minTopK(vector<int>& nums, int k) { MaxHeap maxHeap(k); for (auto& x : nums) { maxHeap.put(x); } return maxHeap.getDatas(); } ``` ### 解法3 利用最大堆思想 ```cpp vector<int> minTopK(vector<int>& nums, int k) { multiset<int, greater<int>> m; for (auto& x : nums) { if (m.size() < k) { m.insert(x); } else { if (x < *m.begin()) { m.erase(m.begin()); m.insert(x); } } } vector<int> result; for (auto& x : m) { result.push_back(x); } return result; } ```