前五科的均分
难度:
标签:
题目描述
代码结果
运行时间: 27 ms, 内存: 16.2 MB
/*
* 题解思路:
* 1. 使用Java Stream API来处理数据。
* 2. 将输入数据转换为Map,其中键是学生ID,值是分数列表。
* 3. 对分数列表进行排序并取前五个分数。
* 4. 计算平均分并返回结果。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int[][] highFive(int[][] items) {
return Arrays.stream(items)
.collect(Collectors.groupingBy(
item -> item[0],
Collectors.mapping(item -> item[1], Collectors.toList())
))
.entrySet().stream()
.map(entry -> {
List<Integer> scores = entry.getValue().stream()
.sorted(Collections.reverseOrder())
.limit(5)
.collect(Collectors.toList());
int avg = (int) scores.stream().mapToInt(Integer::intValue).average().orElse(0);
return new int[]{entry.getKey(), avg};
})
.toArray(int[][]::new);
}
}
解释
方法:
题解的整体思路是使用最小堆(min heap)来存储每个学生的前五个最高分数。首先,使用一个字典(menu)来关联学生的ID和他们的分数列表,其中分数列表是一个最小堆。对于每个成绩项(id_, score),如果该学生的分数堆未满(即少于5个分数),直接将分数加入堆中。如果堆已满,且当前分数大于堆中最小分数,则替换掉堆中的最小分数。这样可以保证堆中始终保持最高的五个分数。遍历完成后,对每个学生的分数求均值,并按照学生ID的升序输出结果。
时间复杂度:
O(n + k log k)
空间复杂度:
O(k)
代码细节讲解
🦆
题解中使用最小堆来维护每个学生的前五个最高分数的逻辑是基于什么考虑?
▷🦆
在堆已满且新分数大于堆中最小分数时,替换最小分数的操作是否可能导致之前的较高分被错误地移除?
▷🦆
题解中提到使用`heapq.heappushpop`进行替换操作,这个函数的工作原理是什么?具体如何实现替换最小分值?
▷