High Five
franklinqin0 ArrayHash TableSort
# Solution
# Priority Queue
Complexity
time:
space:
from collections import defaultdict
from heapq import heappush
def highFive(self, items: List[List[int]]) -> List[List[int]]:
# transform the nested list into a dict
dct = defaultdict(list)
for ID, score in items:
# push in lexicographic order
heappush(dct[ID], score)
if len(dct[ID]) > 5:
# pop the smallest item
heappop(dct[ID])
# sort the dictionary and calc top 5 avg score
res = [[ID, sum(dct[ID]) // 5] for ID in sorted(dct)]
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15