LeetCode 178. 分数排名

Categories:

题目描述
思路分析
1. 解法一：窗口函数 DENSE_RANK（推荐）
2. 解法二：子查询计数
相似题目

题目描述

✅ 178. 分数排名

思路分析

解法一：窗口函数 DENSE_RANK（推荐）

核心思路：

使用 DENSE_RANK() OVER (ORDER BY score DESC) 对分数降序进行稠密排名

稠密排名的特点：相同分数排名相同，排名号连续不跳跃（如 1,2,2,3 而非 1,2,2,4）

RANK() 会跳过排名（1,2,2,4），ROW_NUMBER() 不处理并列，均不满足本题要求

按 score DESC 排序输出结果

复杂度分析：

时间复杂度：O(n log n)，其中 n 为 Scores 表的行数（排序开销）

空间复杂度：O(n)，窗口函数需要全量数据

SELECT
    score,
    -- DENSE_RANK 稠密排名，相同分数排名相同且连续
    DENSE_RANK() OVER (ORDER BY score DESC) AS `rank`
FROM Scores
ORDER BY score DESC;

解法二：子查询计数

核心思路：

对每行分数，统计有多少个不同分数 大于等于 当前分数，即为当前排名

子查询：SELECT COUNT(DISTINCT score) FROM Scores WHERE score >= s.score

不依赖窗口函数，兼容性更好，但性能较差（每行都执行一次子查询）

复杂度分析：

时间复杂度：O(n²)，其中 n 为 Scores 表的行数（每行执行一次子查询）

空间复杂度：O(1)，不需要额外空间

SELECT
    s.score,
    -- 统计有多少个不同分数 >= 当前分数，即为当前排名
    (
        SELECT COUNT(DISTINCT score)
        FROM Scores
        WHERE score >= s.score
    ) AS `rank`
FROM Scores s
ORDER BY s.score DESC;

相似题目

题目	难度	考察点
176. 第二高的薪水	中等	LIMIT、子查询
177. 第N高的薪水	中等	LIMIT OFFSET、函数
185. 部门工资前三高的所有员工	困难	DENSE_RANK、分组
184. 部门工资最高的员工	中等	子查询、分组
1321. 餐馆营业额变化增长	中等	滑动窗口、聚合
1341. 电影评分	中等	聚合、排序

本文作者: HGNULB

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