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

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;
        }
    }
}


############

class Solution {
    public int[][] highFive(int[][] items) {
        int size = 0;
        PriorityQueue[] s = new PriorityQueue[101];
        int n = 5;
        for (int[] item : items) {
            int i = item[0], score = item[1];
            if (s[i] == null) {
                ++size;
                s[i] = new PriorityQueue<>(n);
            }
            s[i].offer(score);
            if (s[i].size() > n) {
                s[i].poll();
            }
        }
        int[][] res = new int[size][2];
        int j = 0;
        for (int i = 0; i < 101; ++i) {
            if (s[i] == null) {
                continue;
            }
            int avg = sum(s[i]) / n;
            res[j][0] = i;
            res[j++][1] = avg;
        }
        return res;
    }

    private int sum(PriorityQueue<Integer> q) {
        int s = 0;
        while (!q.isEmpty()) {
            s += q.poll();
        }
        return s;
    }
}

// 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;
    }
};

class Solution:
    def highFive(self, items: List[List[int]]) -> List[List[int]]:
        s = [None] * 101
        for i, score in items:
            if s[i] is None:
                s[i] = []
            s[i].append(score)
        res = []
        for i, scores in enumerate(s):
            if scores is None:
                continue
            avg = sum(nlargest(5, scores)) // 5
            res.append([i, avg])
        return res

1086 - High Five

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions