面试题40. 最小的k个数

思路：这题应为数据量很小，所以直接sort即可。如果数据去到10**9这种数据量的话，需要用到优先队列，遍历一次数组即可O(n+logn)

笔记：优先队列priority(int, vector<int>, less<int> > q;//从大到小

class Solution {public:vector<int> getLeastNumbers(vector<int>& arr, int k) {vector<int> res;if(k==0) return res;priority_queue<int, vector<int>, less<int> > q;//从大到小(数组逐渐变小)//遍历数组次for(int i=0;i<arr.size();i++){if(i<k) q.push(arr[i]);//先放k个else if(arr[i]<q.top()){ //与优先队列最大的那个比较q.pop();q.push(arr[i]);}}//输出结果for(int i=0;i<k;i++){res.push_back(q.top());q.pop();}return res;}};