LeetCode 1280. 学生们参加各科测试的次数
题目描述
题意分析
每个学生都对应每一门科目，结果必须输出所有“学生、科目”组合，并给出参加测试的次数；从未参加某科测试时也要输出，次数为
0。
Students的学生编号唯一，Subjects的科目名称唯一，而Examinations没有主键：同一学生、同一科目的重复记录表示参加了多次测试，必须逐条计数。最后按学生编号、科目名称排序。
解法：笛卡尔积 + 左连接聚合
核心思路
[!blue]
直接从考试表分组，只能得到至少参加过一次测试的组合。先将学生表与科目表做
CROSS JOIN，让每个学生与每门科目各配对一次，才能得到结果应当展示的完整范围。再以这个组合表为左表，按“学生编号相同且科目名称相同”左连接考试表。某个组合有几条考试记录，就匹配出几行；没有考试记录时，左连接也会保留这个组合，但右表各列为
NULL。按学生和科目分组后，使用
COUNT(e.subject_name)统计右表的非空值。实际匹配的每条考试记录贡献1，未匹配时补出的空行贡献0，因此不需要额外补零。不能使用COUNT(*)，也不能统计左表的科目列，因为它们都会把未匹配的保留行算成一次。
解题步骤
- 用
Students CROSS JOIN Subjects生成全部学生与科目的组合。LEFT JOIN Examinations，在ON中同时匹配学生编号和科目名称。- 按学生编号、学生姓名和科目名称分组，让每个组合只输出一行。
- 用
COUNT(e.subject_name)计算测试次数，并命名为attended_exams。- 按
s.student_id、sub.subject_name升序排列结果。
代码实现
SELECT
s.student_id,
s.student_name,
sub.subject_name,
-- 无匹配时此列为空，统计非空列得到零而不是一
COUNT(e.subject_name) AS attended_exams
FROM Students AS s
-- 先生成所有学生与科目的组合，包括从未考试者
CROSS JOIN Subjects AS sub
-- 同时按学生和科目匹配，保留没有对应考试的组合
LEFT JOIN Examinations AS e
ON e.student_id = s.student_id
AND e.subject_name = sub.subject_name
GROUP BY s.student_id, s.student_name, sub.subject_name
ORDER BY s.student_id, sub.subject_name;
复杂度分析
- 时间复杂度：设学生数
S、科目数C、流水数E。哈希连接与聚合的常见估算为 $O(SC+E)$，结果排序另为 $O(SC\log(SC+1))$，实际取决于执行计划。- 空间复杂度：中间连接与分组的常见上界为 $O(SC+E)$，由数据库所选算法决定。
关键点总结
[!green]
CROSS JOIN决定应当显示哪些组合，LEFT JOIN为每个组合补充考试记录。- 分组后统计右表的非空列，能同时正确处理多次考试与零次考试。
- 考试表中的重复行是有效次数，不能去重。
易错点总结
[!yellow]
- 从考试表直接分组或改成内连接，都会漏掉零次考试的组合。
COUNT(*)和COUNT(sub.subject_name)都会把左连接补出的行计为1；需要统计e中用于匹配的列。- 不要使用
COUNT(DISTINCT e.subject_name)，同一科目参加多次测试也必须计为多次。- 连接条件缺少学生编号或科目名称，都会把其他组合的考试记录混入当前计数。
- 在
WHERE中要求右表字段非空，会把左连接保留下来的零次组合再次过滤掉。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 175. 组合两个表 | 简单 | 先保留每个学生与科目的全部组合，再左连接实际考试记录，缺考组合也必须出现。 |
| 182. 查找重复的电子邮箱 | 简单 | 同样分组计数，但本题外连接补出的空行不能算一次考试，应计右表实际匹配记录。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！