0178. Rank Scores

题目信息

题号:
  1. 分数排名

难度:

Medium

主题:

Database、窗口函数、密集排名

原题:

LeetCode 0178

重点:

将名次定义为不低于当前值的不同分数数量,用 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);合适的降序索引可能帮助读取顺序。 与逐行相关子查询相比,窗口方案避免为每条记录重新扫描并统计更高的不同分数。