1074. High Five

• Difficulty: Easy

• Topics: Array, Hash Table, Sort

• Similar Questions:

Problem:

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. 1 <= items.length <= 1000
2. items[i].length == 2
3. The IDs of the students is between 1 to 1000
4. The score of the students is between 1 to 100
5. For each student, there are at least 5 scores

Solutions:

class Solution {
public:
    vector<vector<int>> highFive(vector<vector<int>>& items) {
        map<int, priority_queue<int, vector<int>, greater<int>>> studentToScores;

        for (auto& item : items) {
            int id = item[0];
            int score = item[1];
            studentToScores[id].push(score);
            if (studentToScores[id].size() > 5) {
                studentToScores[id].pop();
            }
        }

        vector<vector<int>> ret;
        for (auto& entry : studentToScores) {
            int sum = 0;
            for (int i = 0; i < 5; ++i) {
                sum += entry.second.top(); entry.second.pop();
            }

            ret.push_back({entry.first, sum/5});
        }

        return ret;
    }
};