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][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

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

Java

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

All Problems

All Solutions