JZ40-题解 | #最小的K个数#
最小的K个数
http://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
题目描述
给定一个长度为 n 的可能有重复值的数组,找出其中不去重的最小的 k 个数。
例如数组元素是4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4(任意顺序皆可)。
题解1:排序
代码
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
sort(input.begin(), input.end());
vector<int> v;
for (int i = 0; i < k; i++) {
v.push_back(input[i]);
}
return v;
}
题解2:大根堆
普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。
在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。小根堆的定义:
priority_queue<int,vector,greater> small;
大根堆的定义:
priority_queue big;
代码
//小根堆的定义:
// priority_queue<int,vector<int>,greater<int>> small;
//大根堆的定义:
//priority_queue<int> big;
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> v;
if (input.size() == 0 || k == 0) return v;
priority_queue<int> queue;
for (int i = 0; i < input.size(); i++) {
queue.push(input[i]);//大根堆中插入的元素会自动按照递增的顺序排序
if (queue.size() > k)
queue.pop();//弹出queue中最大元素
}
while (!queue.empty()) {
v.push_back(queue.top());
queue.pop();
}
return v;