Question
Formatted question description: https://leetcode.ca/all/1086.html
1086. 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 <= items.length <= 1000
items[i].length == 2
The IDs of the students is between 1 to 1000
The score of the students is between 1 to 100
For each student, there are at least 5 scores
Algorithm
There may be many scores for a person in the input array, but all you want is the average score of the highest five scores for each different id.
So the method is to create a hashmap, the key is the id of each person, and the value is a priority queue to store each person’s top five scores.
For this question, you need to traverse the array and store the data; then traverse the hashmap keyset, calculate the average score of each person’s top five scores according to each key, and then output it as a twodimensional array.
Time O(nlogn)
Space O(n)
Code
Java

public class High_Five { class Solution { public int[][] highFive(int[][] items) { HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<>(); for (int[] i : items) { int id = i[0]; int score = i[1]; PriorityQueue<Integer> queue = map.get(id); if (queue == null) { queue = new PriorityQueue<>(5); map.put(id, queue); } queue.offer(score); if (queue.size() > 5) { queue.poll(); } } int index = 0; int[][] res = new int[map.size()][2]; for (int id : map.keySet()) { PriorityQueue<Integer> queue = map.get(id); int sum = 0; while (!queue.isEmpty()) { sum += queue.poll(); } res[index][0] = id; res[index][1] = sum / 5; index++; } return res; } } }

// OJ: https://leetcode.com/problems/highfive/ // Time: O(NlogN) // Space: O(N) class Solution { public: vector<vector<int>> highFive(vector<vector<int>>& A) { map<int, vector<int>> m; for (auto &v : A) m[v[0]].push_back(v[1]); vector<vector<int>> ans; for (auto &[id, scores] : m) { sort(begin(scores), end(scores), greater()); ans.push_back({ id, accumulate(begin(scores), begin(scores) + 5, 0) / 5 }); } return ans; } };

print("Todo!")