LeetCode 177. 第N高的薪水

Categories:

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

题目描述

✅ 177. 第N高的薪水

思路分析

解法一：LIMIT OFFSET + 子查询去重（推荐）

核心思路：

先在函数内将 N 减 1，得到偏移量 M = N - 1（MySQL 函数体内可直接修改参数）

对薪水去重后降序排列，用 LIMIT 1 OFFSET M 取第 N 高的值

当不足 N 个不同薪水时，LIMIT 返回空集，外层 SELECT 自动返回 NULL

需要包裹一层 SELECT 是因为 LIMIT 不能直接用在函数返回值中

复杂度分析：

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

空间复杂度：O(n)，去重后的薪水集合

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
    -- N 减 1 作为偏移量
    SET N = N - 1;
    RETURN (
        SELECT DISTINCT salary
        FROM Employee
        ORDER BY salary DESC
        LIMIT 1 OFFSET N
    );
END

解法二：窗口函数 DENSE_RANK

核心思路：

使用 DENSE_RANK() 对薪水降序进行稠密排名（相同薪水排名相同，排名连续不跳号）

筛选排名等于 N 的记录，取其薪水

若不存在第 N 高的薪水，子查询返回空，外层返回 NULL

DENSE_RANK 比 RANK 更合适，因为 RANK 会跳过排名号

复杂度分析：

时间复杂度：O(n log n)，其中 n 为 Employee 表的行数

空间复杂度：O(n)，窗口函数需要全表扫描

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
    RETURN (
        SELECT DISTINCT salary
        FROM (
            -- 使用 DENSE_RANK 对薪水稠密排名
            SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
            FROM Employee
        ) ranked
        WHERE rnk = N
        LIMIT 1
    );
END

相似题目

题目	难度	考察点
176. 第二高的薪水	中等	LIMIT、IFNULL
178. 分数排名	中等	DENSE_RANK 窗口函数
185. 部门工资前三高的所有员工	困难	DENSE_RANK、分组
184. 部门工资最高的员工	中等	子查询、分组
1907. 按分类统计薪水	中等	条件聚合

本文作者: HGNULB

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