LeetCode 178. 分数排名

2022-02-20 HGNULB 约 3 分钟

文章信息 6 个分类 · 1 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 字节

标签

数据库

题目描述

✅ 178. 分数排名

题意分析

为 Scores 中的每条成绩计算名次：分数越高，名次越靠前；同分使用相同名次，下一个不同分数的名次紧接着加一。结果仍要保留每条原始成绩记录，并按分数降序输出。

解法：窗口函数稠密排名

核心思路

[!blue]
每条记录的名次等于“比它高的不同分数数量加一”。 因此名次应按不同分数组推进，同分记录不增加后面记录的名次。这正是 DENSE_RANK() 的稠密排名规则。

OVER (ORDER BY score DESC) 不划分独立分区，而是在全表范围内按分数从高到低排名。排序键只有 score，同分行属于同一个并列组；每遇到下一种分数，排名只增加 1，所以不会出现并列后的名次空缺。

窗口函数在每条明细行上附加排名，不会像分组聚合那样合并同分记录。即使输出的 score 和 rank 完全相同，这些行也应全部保留，不能添加 DISTINCT。

窗口内的 ORDER BY 只定义排名如何计算，不保证查询结果以这个顺序返回。最后再写查询级的 ORDER BY score DESC，才能明确满足输出顺序；同分行之间不需要额外区分先后。

解题步骤

1. 从 Scores 中选择每条记录的 score。
2. 用 DENSE_RANK() OVER (ORDER BY score DESC) 计算全表名次，不按分数分区。
3. 将名次列命名为 rank，使用反引号避免与 MySQL 保留字冲突。
4. 在主查询末尾按分数降序返回全部记录。

只有一种分数时，每条记录都排第 1；表为空时结果也为空。两种情况都由窗口函数和原始行集自然处理，无需额外补行或去重。

代码实现

SELECT
    score,
    -- DENSE_RANK 并列同名且名次连续；rank 是保留字必须加反引号。
    DENSE_RANK() OVER (ORDER BY score DESC) AS `rank`
FROM Scores
-- 窗口内排序决定名次，这里的排序决定最终输出顺序。
ORDER BY score DESC;

复杂度分析

• 时间复杂度：通常由排序主导，按 $O(n\log(n+1))$ 估算，实际取决于执行计划。
• 空间复杂度：排序与窗口中间结果通常按 $O(n)$ 估算。

关键点总结

[!green]

• 并列同名且不跳号，对应稠密排名。
• 排名附加在每行明细上，不压缩相同成绩。
• 最终输出顺序由查询级 ORDER BY 明确保证。

易错点总结

[!yellow]

• 改用 RANK：并列之后会跳号。
• 改用 ROW_NUMBER：相同分数也获得不同序号。
• 按 score 分区：每个分数都从第一名开始。
• 输出加 DISTINCT：丢失重复成绩记录。
• 窗口排序再加入 id：同分记录被区分，不再属于同一个并列组。

相似题目

题目	难度	关联与区别
185. 部门工资前三高的所有员工	困难	密集排名适合按不同工资值取每个部门前三名，不应让同分占用多个名次。
176. 第二高的薪水	中等	同样按不同数值区分排名，本题返回每行名次，原题只返回第二种不同值。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/58737551

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！