High Five

题目(LeetCode #1086)

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

题解

使用 PriorityQueue 分别保存每个人的分数，若 queue 长度大于 5 则去掉其中最小的分数。

class Solution {
    public int[][] highFive(int[][] items) {
        Map<Integer, Queue<Integer>> map = new HashMap<>();

        for (int[] item : items) {
            int id = item[0], score = item[1];

            Queue<Integer> curQueue = map.get(id);
            if (curQueue == null) {
                curQueue = new PriorityQueue<>(5);
                map.put(id, curQueue);
            }

            curQueue.add(score);
            if (curQueue.size() > 5) curQueue.poll();
        }

        int[][] result = new int[map.size()][2];
        int idx = 0;
        for (int k : map.keySet()) {
            Queue<Integer> curQueue = map.get(k);
            int sum = 0;
            while (!curQueue.isEmpty()) sum += curQueue.poll();
            result[idx][0] = k;
            result[idx][1] = sum / 5;
            idx++;
        }

        return result;
    }
}