0178. Rank Scores ================= 题目信息 -------- :题号: 0178. 分数排名 :难度: Medium :主题: Database、窗口函数、密集排名 :原题: `LeetCode 0178 `_ :重点: 将名次定义为不低于当前值的不同分数数量,用 DENSE_RANK 保留并列且不留空位 题目重述 -------- ``Scores(id, score)`` 表保存分数记录。输出每条记录的 ``score`` 及其从高到低的排名, 排名列命名为 ``rank``,结果也按 ``score`` 降序排列。 排名采用密集语义:相同分数共享同一名次;下一个更低的不同分数只增加一个名次,不因并列 记录数量而跳号。 自建示例 -------- .. code-block:: text 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 实现 -------- .. code-block:: sql SELECT score, DENSE_RANK() OVER (ORDER BY score DESC) AS `rank` FROM Scores ORDER BY score DESC; 题解 ---- 先把排名写成可检查的定义 ~~~~~~~~~~~~~~~~~~~~~~~~ 对某条分数 ``current``,它的密集名次可以定义为: .. code-block:: text 1 + 严格大于 current 的不同分数数量 例如严格大于 8.75 的不同分数只有 9.20,所以 8.75 排名为 2。两条 8.75 看到的更高 不同值集合完全相同,自然共享名次;7.10 上方有 9.20、8.75 两个不同值,所以排名为 3, 不会被重复行推到第 5。 按这个定义,可以为外层每一行执行一个相关子查询,对更高分数做 ``COUNT(DISTINCT score)``。它正确,却会对大量重叠数据重复计数和去重。窗口函数让数据库 只建立一次全局分数顺序,再把排名映射回每条原始记录。 三个相似窗口函数的差别 ~~~~~~~~~~~~~~~~~~~~~~~~ 按 ``score DESC`` 排序后,常见函数有三种不同语义: .. code-block:: text 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`` 使用反引号作为别名,是因为该单词可能与数据库关键字产生歧义。 具体走读 ~~~~~~~~ 示例按分数降序形成三个同值组: .. code-block:: text 第 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)``;合适的降序索引可能帮助读取顺序。 与逐行相关子查询相比,窗口方案避免为每条记录重新扫描并统计更高的不同分数。