题目描述：
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：0≤k,n≤10000，数组中每个数的大小0≤val≤1000
要求：空间复杂度 O(n) ，时间复杂度O(nlogk)
示例：
输入：
[4,5,1,6,2,7,3,8],4
返回值：
[1,2,3,4]
说明：
返回最小的4个数即可，返回[1,3,2,4]也可以
解题思路：
本题是排序题目。两种解题思路。
1）快速排序
快速排序后取前k个值，时间复杂度O(nlogn)，空间复杂度O(k)，时间复杂度不满足题目要求的O(nlogk)，说明题目想考察的不是快速排序。
2）基于优先队列的堆排序
使用优先队列，遍历vector复杂度为n，每次进行插入，插入基于堆排序实现（二分思想），又因为队列的数据被我们保持在k个，所以插入复杂度为logk，时间总复杂度O(nlogk)。空间上，可以将input清空节省空间，不需要临时空间，空间复杂度O(1)。
测试代码：
1）快速排序
class Solution { public: // 获取最小K数 vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) { int size = int(input.size()); // 快排 sort(input.begin(), input.end()); // 取k和size更小值，放置越界 int r = min(k, size); // 获取结果 vector<int> result; for(int i = 0; i < r; ++i){ result.push_back(input[i]); } return result; } };
2）基于优先队列的堆排序
#include <queue> class Solution { public: // 获取最小K数 vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) { int size = int(input.size()); // 创建优先队列，默认采用less模式，即最大值作为优先级最高的值优先被推出，更小值保留在队列中 priority_queue<int> q; // 遍历vector for(int i = 0; i < size; ++i){ // 往优先队列中存数据时，已经进行了堆排序，插入的复杂度为logk q.push(input[i]); // 保持队列中只有k个数据，可以使插入的效率提高 if(q.size() > k){ // 最大值被推出 q.pop(); } } // 清空vector，节省空间 input.clear(); // 将优先队列中的数据放入vector while(!q.empty()){ input.push_back(q.top()); q.pop(); } return input; } };
