Lintcode 613. 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.

Example

Example 1:

Input: 
[[1,91],[1,92],[2,93],[2,99],[2,98],[2,97],[1,60],[1,58],[2,100],[1,61]]
Output:
1: 72.40
2: 97.40

Example 2:

Input:
[[1,90],[1,90],[1,90],[1,90],[1,90],[1,90]]
Output: 
1: 90.00

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

/**  * 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         if (results == null || results.length == 0) {             return new HashMap<Integer, Double>();         }                   Map<Integer, PriorityQueue<Integer>> studentToScoreMap = new HashMap<>();         for (Record record : results) {             PriorityQueue<Integer> pq = studentToScoreMap.getOrDefault(record.id, new PriorityQueue<>());             pq.offer(record.score);             if (pq.size() > 5) {                 pq.poll();             }             studentToScoreMap.put(record.id, pq);         }                   Map<Integer, Double> ans = new HashMap<>();         for (Integer id : studentToScoreMap.keySet()) {             PriorityQueue<Integer> scores = studentToScoreMap.get(id);             double ave = getAverageScore(scores);             ans.put(id, ave);         }                   return ans;     }           private double getAverageScore(PriorityQueue<Integer> scores) {         int sum = 0;         int numScores = scores.size();         while (!scores.isEmpty()) {             sum += scores.poll();         }                   return (double) sum / numScores;     } }