High Five

There are two properties in the node student id and scores, to ensure that each student will have at least 5 points, find the average of 5 highest scores for each person.

算是一个OOD的题吧
求 k highest 自然想到 priority queue
size of the queue k = 5
每次加入数 peek() 是 O(1), poll O(logk), offer O(logk)
所以全部都是constant的
九章答案里用的是LinkedList每次操作是把现有的5个score扫一遍求min，O(k)，在这道题里当然也是constant
但是我从直观上感觉priority queue是不是overhead会比linkedlist多一点？存疑
从general的时间复杂度来说还是pq好

最后循环我用了keySet，感觉改进一下用entrySet会看着neat一点

/**
 * Definition for a Record
 * class Record {
 *     public int id, score;
 *     public Record(int id, int score){
 *         this.id = id;
 *         this.score = score;
 *     }
 * }
 */
public class Solution {
    /**
     * @param results a list of <student_id, score>
     * @return find the average of 5 highest scores for each person
     * Map<Integer, Double> (student_id, average_score)
     */
    public Map<Integer, Double> highFive(Record[] results) {
        // Write your code here
        Map<Integer, Double> average = new HashMap<>();
        if (results == null || results.length == 0) return average;
        //Keep a priority queue to record the scores of each student
        Map<Integer, PriorityQueue<Integer>> highestFiveScores = new HashMap<>();
        for (int i = 0; i < results.length; i++) {
            int currId = results[i].id;
            int currScore = results[i].score;
            PriorityQueue<Integer> currPQ;
         
            if (highestFiveScores.containsKey(currId)) {
                currPQ = highestFiveScores.get(currId);
                if (currPQ.size() < 5) {
                    currPQ.offer(currScore);
                } else if (currScore > currPQ.peek()) {
                    currPQ.poll();
                    currPQ.offer(currScore);
                }
            } else {
                currPQ = new PriorityQueue<Integer>();
                currPQ.offer(currScore);
                highestFiveScores.put(currId, currPQ);
            }
        }
        for (Integer id : highestFiveScores.keySet()) {
            PriorityQueue<Integer> pq = highestFiveScores.get(id);
            if (pq.size() < 5) continue;
            Iterator<Integer> iter = pq.iterator();
            int sumFive = 0;
            while (iter.hasNext()) {
                sumFive += iter.next();
            }
            Double ave = sumFive / 5.0;
            average.put(id, ave);
        }
        return average;
    }
}