如何优化学生最佳平均分计算函数的时间复杂度？

你的当前实现确实存在两次遍历的问题：先用集合提取所有学生，再对每个学生完整遍历一遍成绩列表筛选分数，这会导致时间复杂度达到O(n*m)（n是学生数量，m是总成绩记录数），处理大规模输入时效率会很低。

优化思路：用哈希表（字典）一次遍历完成统计 #

我们可以用字典实时记录每个学生的总分和成绩数量，只需要遍历一次成绩列表就能完成所有统计，之后再遍历字典计算平均分并找出最大值，总时间复杂度降到O(m)（m是总记录数），这是更优的线性时间复杂度。

优化后的代码实现 #

import math

def bestAverageGrade(scores):
    if not scores:
        return 0
    
    student_stats = {}
    for name, grade_str in scores:
        grade = int(grade_str)
        if name in student_stats:
            total, count = student_stats[name]
            student_stats[name] = [total + grade, count + 1]
        else:
            student_stats[name] = [grade, 1]
    
    max_average = -float('inf')
    for total, count in student_stats.values():
        average = total / count
        if average > max_average:
            max_average = average
    
    return math.floor(max_average)

代码说明 #

1. 边界处理：先判断输入是否为空，直接返回0，符合题目要求。
2. 一次遍历统计：遍历每条成绩记录时，将成绩转换为整数（题目说明成绩是正负整数，用int比float更高效），然后更新字典中对应学生的总分和成绩计数：
   • 学生不在字典中时，初始化总分为当前成绩、计数为1；
   • 学生已存在时，累加成绩到总分、计数加1。
3. 计算最大平均分：遍历字典中的统计数据，计算每个学生的平均分并记录最大值，最后对最大值做向下取整返回。

复杂度分析 #

• 时间复杂度：O(m)，仅需遍历一次所有成绩记录，再遍历一次所有学生（学生数≤总记录数），整体为线性时间。
• 空间复杂度：O(k)，k是不同学生的数量，用于存储统计信息，属于必要的空间开销。

用你的示例输入测试：

scores = [["Bobby", "87"], ["Charles", "100"], ["Eric", "64"], ["Charles", "22"]]
print(bestAverageGrade(scores))  # 输出87，符合预期

内容的提问来源于stack exchange，提问作者walkerous