返回

简单的topK问题

发布时间:2023-08-17 00:01:23 283

问题描述:

给定一个长度为 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;
}
};

简单的topK问题_数组_08

 

 

特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报
评论区(0)
按点赞数排序
用户头像
精选文章
thumb 中国研究员首次曝光美国国安局顶级后门—“方程式组织”
thumb 俄乌线上战争,网络攻击弥漫着数字硝烟
thumb 从网络安全角度了解俄罗斯入侵乌克兰的相关事件时间线
下一篇
【C语言】指针从初识到使用详解 2023-08-16 21:04:30