面试题 17.14. 最小K个数

😀最近新创建了个开源仓库，总结LeetCode的每日一题，目前已有C++、JavaScript语言版本，欢迎大家提供其他语言版本！

🩲仓库地址：每日一题系列

题目描述：

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4输出： [1,2,3,4]

解答：

C++：

方法一

优先队列 可以看295. 数据流的中位数

class Solution {public:vector<int> smallestK(vector<int>& arr, int k) {/*sort(arr.begin(),arr.end());return vector<int>(arr.begin(),arr.begin()+k);*///优先队列if(k==0) return {};priority_queue<int> res;for(auto &x:arr){if(res.size()<k){res.push(x);}else{if(x<res.top()){res.pop();res.push(x);}}}vector<int> ans;while(!res.empty()){ans.push_back(res.top());res.pop();}reverse(ans.begin(),ans.end());return ans;}};

方法二

排序

class Solution {public:vector<int> smallestK(vector<int>& arr, int k) {sort(arr.begin(),arr.end());return vector<int>(arr.begin(),arr.begin()+k);}};