简单的topK问题
发布时间:2023-08-17 00:01:23 282 相关标签:
问题描述:
给定一个长度为 n 的可能有重复值的数组,找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4(任意顺序皆可)数据范围:,数组中每个数的大小要求:空间复杂度 ,时间复杂度
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> v;
if (input.size() == 0 || k <= 0)
return v;
if (k > (int)input.size())
return input;
// 这里 建大堆 默认的 less 就是 大堆
std::priority_queue<int> maxPri;
for (int i = 0; i < k; i++) {
maxPri.push(input[i]);
}
// 这里开始 挑选
for (size_t i = k; i < input.size(); i++) {
// 得到 堆顶的元素
int ret = maxPri.top();
// 判断 是否入堆
if (input[i] < ret) {
maxPri.pop();
maxPri.push(input[i]);
}
}
while (!maxPri.empty()) {
v.push_back(maxPri.top());
maxPri.pop();
}
return v;
}
};

文章来源: https://blog.51cto.com/byte/5730516
特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报