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

我的数据结构与算法题目集代码仓：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<iostream>
#include<queue>
#include<vector>

using namespace std;

int N, M;

int main(){
	scanf("%d %d", &N, &M);
	priority_queue<int, vector<int>, greater<int>> 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<int> 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("\n");
		}
	}
	return 0;
}

C++解题报告：