# 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] the student's id, and items[i] 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 two-dimensional array.

Time O(nlogn)

Space O(n)

# Code

• 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;
int score = i;
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()];
for (int id : map.keySet()) {
PriorityQueue<Integer> queue = map.get(id);
int sum = 0;
while (!queue.isEmpty()) {
sum += queue.poll();
}
res[index] = id;
res[index] = sum / 5;
index++;
}
return res;
}
}
}

############

class Solution {
public int[][] highFive(int[][] items) {
int size = 0;
PriorityQueue[] s = new PriorityQueue;
int n = 5;
for (int[] item : items) {
int i = item, score = item;
if (s[i] == null) {
++size;
s[i] = new PriorityQueue<>(n);
}
s[i].offer(score);
if (s[i].size() > n) {
s[i].poll();
}
}
int[][] res = new int[size];
int j = 0;
for (int i = 0; i < 101; ++i) {
if (s[i] == null) {
continue;
}
int avg = sum(s[i]) / n;
res[j] = i;
res[j++] = avg;
}
return res;
}

private int sum(PriorityQueue<Integer> q) {
int s = 0;
while (!q.isEmpty()) {
s += q.poll();
}
return s;
}
}

• // OJ: https://leetcode.com/problems/high-five/
// 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].push_back(v);
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;
}
};

• class Solution:
def highFive(self, items: List[List[int]]) -> List[List[int]]:
s = [None] * 101
for i, score in items:
if s[i] is None:
s[i] = []
s[i].append(score)
res = []
for i, scores in enumerate(s):
if scores is None:
continue
avg = sum(nlargest(5, scores)) // 5
res.append([i, avg])
return res