LeetCode 177. 第N高的薪水

2022-02-11 HGNULB 约 3 分钟

文章信息 6 个分类 · 1 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 字节

标签

数据库

题目描述

✅ 177. 第N高的薪水

题意分析

实现函数，从 Employee 中返回第 N 高的不同薪水值，名次从 1 开始。多个员工薪水相同时只占一个名次；如果不同薪水不足 N 种，函数返回 NULL。

解法：去重排序 + 偏移查询

核心思路

[!blue]
先确定排名对象，再定位第 N 项。 DISTINCT salary 把重复薪水合并成一个值，ORDER BY salary DESC 再按从高到低排列。此时每一行恰好代表一个名次，排名不再受同薪员工人数影响。

MySQL 的 LIMIT offset, count 表示先跳过 offset 行，再取至多 count 行。第 N 高前面有 N-1 个不同薪水，因此先执行 SET N=N-1，将参数改作偏移量，再用 LIMIT N,1 取剩余的第一项。

RETURN 中的查询作为标量子查询使用：只有一个结果时返回该薪水，没有结果时返回 NULL。LIMIT 1 保证不会出现多行，空表或不同薪水数量不足也无需额外查询判断。

解题步骤

1. 在函数体中把 N 减一，后续的 N 表示需要跳过的行数。
2. 对 salary 去重并降序排列。
3. 跳过 N 行后最多取一行，通过标量子查询返回。

原名次为 1 时偏移为 0，直接取得最高薪水。若去重后的行数少于原名次，跳过之后没有可取的行，函数结果为 NULL，不能用 0 替代。

代码实现

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
    -- 序号从 1 起、偏移量从 0 起，先把两者对齐。
    SET N = N - 1;
    RETURN (
        -- DISTINCT 压平并列；N 已转换为从 0 开始的偏移量。
        SELECT DISTINCT salary
        FROM Employee
        ORDER BY salary DESC
        LIMIT N, 1
    );
END

复杂度分析

• 时间复杂度：取决于执行计划；无有序访问路径时，扫描、去重和排序通常按 $O(n\log(n+1))$ 估算。
• 空间复杂度：排序与去重的中间空间通常按 $O(n)$ 上界估算，具体取决于执行计划。

关键点总结

[!green]

• 排名对象是不同薪水值，不是员工行。
• 序号从一开始，偏移从零开始。
• 标量空查询返回 NULL，无需替换成其他值。

易错点总结

[!yellow]

• 省略去重：并列薪水占用多个位置。
• N 不减一：取到下一名。
• 漏掉降序：取成第 N 低。
• 无解用零兜底：题目要求返回 NULL。

相似题目

题目	难度	关联与区别
176. 第二高的薪水	中等	第二高是N=2的特例，两题都需先消除相同工资值对名次的重复占用。
185. 部门工资前三高的所有员工	困难	原题按部门分别取前几种工资，本题在全表范围只取第N种不同工资。

转载与许可

作者 HGNULB

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

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！