数据结构与算法题目集7-38??寻找大富翁

发布于:2021-10-21 07:49:45

我的数据结构与算法题目集代码仓:https://github.com/617076674/Data-structure-and-algorithm-topic-set


原题链接:https://pintia.cn/problem-sets/15/problems/865


题目描述:



知识点:优先队列


思路:用一个大小为M的优先队列维护最大的M个数

时间复杂度是O(NlogM)。空间复杂度是O(M)。


C++代码:


#include
#include
#include

using namespace std;

int N, M;

int main(){
scanf("%d %d", &N, &M);
priority_queue, greater> q;
for(int i = 0; i < N; i++){
int num;
scanf("%d", &num);
if(q.size() < M){
q.push(num);
}else if(q.top() < num){
q.pop();
q.push(num);
}
}
vector result;
while(!q.empty()){
result.push_back(q.top());
q.pop();
}
for(int i = result.size() - 1; i >= 0; i--){
printf("%d", result[i]);
if(i != 0){
printf(" ");
}else{
printf("
");
}
}
return 0;
}

C++解题报告:



?

相关推荐

最新更新

猜你喜欢