难度: Easy
Submission
运行时间: 27 ms
内存: 16.2 MB
class Solution:
def highFive(self, items: List[List[int]]) -> List[List[int]]:
import heapq
limit = 5
menu = dict()
for id_, score in items:
menu.setdefault(id_, [])
min_heap = menu[id_]
if len(min_heap) < limit:
heapq.heappush(menu[id_], score)
elif score > min_heap[0]:
heapq.heappushpop(menu[id_], score)
res = []
for id_ in sorted(menu.keys()):
scores = menu[id_]
mean = sum(scores) // len(scores)
res.append([id_, mean])
# print(res)
return res
Explain
题解的整体思路是使用最小堆(min heap)来存储每个学生的前五个最高分数。首先，使用一个字典(menu)来关联学生的ID和他们的分数列表，其中分数列表是一个最小堆。对于每个成绩项(id_, score)，如果该学生的分数堆未满（即少于5个分数），直接将分数加入堆中。如果堆已满，且当前分数大于堆中最小分数，则替换掉堆中的最小分数。这样可以保证堆中始终保持最高的五个分数。遍历完成后，对每个学生的分数求均值，并按照学生ID的升序输出结果。
时间复杂度: O(n + k log k)
空间复杂度: O(k)
class Solution:
def highFive(self, items: List[List[int]]) -> List[List[int]]:
import heapq
limit = 5 # 设置每个学生的分数列表大小限制为5
menu = dict() # 学生ID到其分数堆的映射
for id_, score in items:
menu.setdefault(id_, []) # 确保每个学生ID都有对应的分数堆
min_heap = menu[id_] # 获取当前学生的分数堆
if len(min_heap) < limit:
heapq.heappush(menu[id_], score) # 堆未满，直接添加新分数
elif score > min_heap[0]:
heapq.heappushpop(menu[id_], score) # 堆已满，且新分数大于堆中最小分数，替换之
res = [] # 结果列表
for id_ in sorted(menu.keys()): # 按学生ID排序
scores = menu[id_] # 获取学生的分数堆
mean = sum(scores) // len(scores) # 计算均值
res.append([id_, mean]) # 添加到结果列表
return res # 返回结果
Explore
使用最小堆的逻辑基于其能高效地维护一组元素中的最小值。在维护学生的前五个最高分时，最小堆让我们能够快速获取当前五个最高分中的最小分数，这样每当有新的分数加入时，我们可以与堆顶的最小分数比较。如果新分数更高，就替换掉这个最小分数，保证堆中始终是当前最高的五个分数。这种方法比存储所有分数后排序要高效得多，尤其是当数据量大时。
不会。在这种情况下，堆中的最小分数是当前堆中五个最高分中的最低者。如果新的分数大于这个最小分数，替换它是正确的，因为新分数成为了新的五个最高分之一。这种操作保证了堆中始终包含当前最高的五个分数。不会错误地移除原有的较高分数，只是替换了原来的最低分（在最高五分中为最低）以维护堆的属性。
`heapq.heappushpop`函数是一个高效的方式来同时执行推入和弹出操作，主要用于维护固定大小的最小堆。当需要添加一个新元素到已满的堆中并且要保持堆的大小不变时使用。此函数首先将新元素推入堆中，然后立即弹出堆中的最小元素。这种操作确保如果新元素小于等于堆中的最小元素，它会被立即弹出，否则，堆中原有的最小元素会被弹出，新元素则被添加。这样，堆始终维护在预设的大小，且总是包含最大的最小元素（即在本题中的前五高分）。