0178. Rank Scores¶
题目信息¶
- 题号:
分数排名
- 难度:
Medium
- 主题:
Database、窗口函数、密集排名
- 原题:
- 重点:
将名次定义为不低于当前值的不同分数数量,用 DENSE_RANK 保留并列且不留空位
题目重述¶
Scores(id, score) 表保存分数记录。输出每条记录的 score 及其从高到低的排名,
排名列命名为 rank,结果也按 score 降序排列。
排名采用密集语义:相同分数共享同一名次;下一个更低的不同分数只增加一个名次,不因并列 记录数量而跳号。
自建示例¶
Scores:
id | score
1 | 9.20
2 | 8.75
3 | 9.20
4 | 7.10
5 | 8.75
输出:
score | rank
9.20 | 1
9.20 | 1
8.75 | 2
8.75 | 2
7.10 | 3
SQL 实现¶
SELECT
score,
DENSE_RANK() OVER (ORDER BY score DESC) AS `rank`
FROM Scores
ORDER BY score DESC;
题解¶
先把排名写成可检查的定义¶
对某条分数 current,它的密集名次可以定义为:
1 + 严格大于 current 的不同分数数量
例如严格大于 8.75 的不同分数只有 9.20,所以 8.75 排名为 2。两条 8.75 看到的更高 不同值集合完全相同,自然共享名次;7.10 上方有 9.20、8.75 两个不同值,所以排名为 3, 不会被重复行推到第 5。
按这个定义,可以为外层每一行执行一个相关子查询,对更高分数做
COUNT(DISTINCT score)。它正确,却会对大量重叠数据重复计数和去重。窗口函数让数据库
只建立一次全局分数顺序,再把排名映射回每条原始记录。
三个相似窗口函数的差别¶
按 score DESC 排序后,常见函数有三种不同语义:
ROW_NUMBER:每一行编号不同,9.20 会得到 1、2
RANK: 并列同名次,但后面留空,8.75 可能排 3
DENSE_RANK:并列同名次,后面不留空,8.75 排 2
题目同时要求“相同分数同名次”和“后续名次连续”,只有 DENSE_RANK 直接满足。
OVER (ORDER BY score DESC) 定义窗口内部从高到低比较,且没有 PARTITION BY,
因为所有记录要在同一个全局排名中竞争。
为什么不能先去重输出¶
排名基于不同分数等级,但输出对象仍是 Scores 的每条记录。若在外层使用
SELECT DISTINCT score,两条 9.20 会被合并,只剩一行,违反输出合同。
DENSE_RANK 只在计算名次时把相同排序键视为同一组,不会删除原始行。于是每条记录都
保留,而同组记录得到相同的窗口结果。这正好把“计算时按等级、输出时按记录”两种粒度
分开。
窗口顺序与结果顺序¶
窗口中的 ORDER BY score DESC 决定数字如何排名,但它不承诺最终结果集的物理输出
顺序。外层再次写 ORDER BY score DESC,才明确满足题目要求的展示顺序。
同分行之间没有额外次序要求,且它们的 score、rank 完全相同,所以无需再按
id 排列。rank 使用反引号作为别名,是因为该单词可能与数据库关键字产生歧义。
具体走读¶
示例按分数降序形成三个同值组:
第 1 个不同值组:9.20,共 2 行 -> rank 1
第 2 个不同值组:8.75,共 2 行 -> rank 2
第 3 个不同值组:7.10,共 1 行 -> rank 3
窗口函数遇到相同排序键时保持当前密集名次;只有分数下降到一个此前未见的新值时,名次才 加一。它处理的是组序号,不是已经输出了多少行。
执行代价¶
逻辑上数据库需要按 score 建立全局顺序,再对同值组分配密集名次。无可利用索引时,
排序通常为 O(n log n),窗口扫描为 O(n);合适的降序索引可能帮助读取顺序。
与逐行相关子查询相比,窗口方案避免为每条记录重新扫描并统计更高的不同分数。