[LeetCode] 1086. High Five

Given a list of the scores of different students, items, where items[i] = [IDi, scorei] represents one score from a student with IDi, calculate each student's top five average.

Return the answer as an array of pairs result, where result[j] = [IDj, topFiveAveragej] represents the student with IDj and their top five average. Sort result by IDj in increasing order.

A student's top five average is calculated by taking the sum of their top five scores and dividing it by 5 using integer division.

Example 1:

Input: items = [[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 student with ID = 1 got scores 91, 92, 60, 65, 87, and 100. Their top five average is (100 + 92 + 91 + 87 + 65) / 5 = 87.
The student with ID = 2 got scores 93, 97, 77, 100, and 76. Their top five average is (100 + 97 + 93 + 77 + 76) / 5 = 88.6, but with integer division their average converts to 88.

Example 2:

Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]

Constraints:

1 <= items.length <= 1000
items[i].length == 2
1 <= IDi <= 1000
0 <= scorei <= 100
For each IDi, there will be at least five scores.

前五科的均分。

题意是给一个二维数组，里面包含了一些人的考试成绩，以 [id, score] 的形式给出。请你返回一个二维数组，表示每个 id 的最高的五个分数的平均分。

这个题写的有点绕但是其实思路非常简单。input 数组里面有可能给了一个人的很多分数，但是你要求的只是每个不同 id 的最高的五个分数的平均分。所以做法是创建一个 hashmap，key 是每个人的 id，value 是一个 priority queue，来存储每个人的前五高的分数。这道题你需要遍历一遍数组，将数据存入；接着再遍历 hashmap 的 keyset，根据每个 key，算出每个人的前五高的分数的平均分，然后再以二维数组的形式输出。

时间O(nlogn)

空间O(n)

Java实现

 1 class Solution {
 2     public int[][] highFive(int[][] items) {
 3         HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<>();
 4         for (int[] i : items) {
 5             int id = i[0];
 6             int score = i[1];
 7             PriorityQueue<Integer> queue = map.get(id);
 8             if (queue == null) {
 9                 queue = new PriorityQueue<>(5);
10                 map.put(id, queue);
11             }
12             queue.offer(score);
13             if (queue.size() > 5) {
14                 queue.poll();
15             }
16         }
17 
18         int index = 0;
19         int[][] res = new int[map.size()][2];
20         for (int id : map.keySet()) {
21             PriorityQueue<Integer> queue = map.get(id);
22             int sum = 0;
23             while (!queue.isEmpty()) {
24                 sum += queue.poll();
25             }
26             res[index][0] = id;
27             res[index][1] = sum / 5;
28             index++;
29         }
30         return res;
31     }
32 }

LeetCode 题目总结