leetcode
leetcode 951 ~ 1000
前五科的均分

前五科的均分

难度:

标签:

题目描述

代码结果

运行时间: 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`进行替换操作,这个函数的工作原理是什么?具体如何实现替换最小分值?
`heapq.heappushpop`函数是一个高效的方式来同时执行推入和弹出操作,主要用于维护固定大小的最小堆。当需要添加一个新元素到已满的堆中并且要保持堆的大小不变时使用。此函数首先将新元素推入堆中,然后立即弹出堆中的最小元素。这种操作确保如果新元素小于等于堆中的最小元素,它会被立即弹出,否则,堆中原有的最小元素会被弹出,新元素则被添加。这样,堆始终维护在预设的大小,且总是包含最大的最小元素(即在本题中的前五高分)。

相关问题