题目地址：https://leetcode-cn.com/problems/high-five/
题目描述
Given a list of scores of different students, return the average score of each student's top five scores in the order of each student's id.
Each entry items[i] has items[i][0] the student's id, and items[i][1] the student's score. The average score is calculated using integer division.
Example 1:
Input: [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]
Output: [[1,87],[2,88]]
Explanation:
The average of the student with id = 1 is 87.
The average of the student with id = 2 is 88.6. But with integer division their average converts to 88.
Note:
1、 1<=items.length<=1000；
2、 items[i].length==2；
3、 TheIDsofthestudentsisbetween1to1000；
4、 Thescoreofthestudentsisbetween1to100；
5、 Foreachstudent,thereareatleast5scores；
题目大意
给你一个不同学生的分数列表，请按 学生的 id 顺序 返回每个学生 最高的五科 成绩的 平均分。 对于每条 items[i] 记录， items[i][0] 为学生的 id，itemsiopen in new window 为学生的分数。平均分请采用整数除法计算。
解题方法
大根堆
给每个学生一个大根堆，把其所有的成绩都放入堆中，最后堆中最大的5个数字就是最高的5科成绩。
C++代码如下：
class Solution {
public:
vector<vector<int>> highFive(vector<vector<int>>& items) {
vector<priority_queue<int>> scores(1010);
for (auto& item : items) {
scores[item[0]].push(item[1]);
}
vector<vector<int>> res;
for (int i = 0; i < scores.size(); ++i) {
auto& queue = scores[i];
if (queue.empty()) continue;
int sum = 0;
for (int j = 0; j < 5; ++j) {
sum += queue.top(); queue.pop();
}
res.push_back({i, sum / 5});
}
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发