1086. High Five

 一刷 06/2022

Version #1 Min Heap

Time - N items, collect top 5 -> O(Nlog5) ~ O(N), sort students O(NlogN) -> Total O(NlogN)

Space O(N)

class Solution {

    private static int TOP_COUNT = 5;

    public int[][] highFive(int[][] items) {

        // key-id, que-minHeap of size scores, max size is 5

        Map<Integer, Queue<Integer>> map = new HashMap<>();

        for(int[] item : items) {

            Queue<Integer> minHeap = map.getOrDefault(item[0], new PriorityQueue<>());

            minHeap.offer(item[1]);

            if (minHeap.size() > TOP_COUNT) {

                minHeap.poll();

            }

            map.put(item[0], minHeap);

        }

        int[][] result = new int[map.size()][2];

        int index = 0;

        for (Map.Entry<Integer, Queue<Integer>> entry : map.entrySet()) {

            int sum = 0;

            for (Integer score : entry.getValue()) {

                sum += score;

            }

            result[index++] = new int[]{entry.getKey(), sum / 5};

        }

        Arrays.sort(result, (a, b) -> a[0] - b[0]);

        return result;

    }

}