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;
            }
        }
    }
    
    
  • // OJ: https://leetcode.com/problems/high-five/
    // Time: O(NlogN)
    // Space: O(N)
    class Solution {
    public:
        vector<vector<int>> highFive(vector<vector<int>>& A) {
            map<int, vector<int>> m;
            for (auto &v : A) m[v[0]].push_back(v[1]);
            vector<vector<int>> ans;
            for (auto &[id, scores] : m) {
                sort(begin(scores), end(scores), greater());
                ans.push_back({ id, accumulate(begin(scores), begin(scores) + 5, 0) / 5 });
            }
            return ans;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions