0177. Nth Highest Salary¶
题目信息¶
- 题号:
第 N 高的薪水
- 难度:
Medium
- 主题:
Database、存储函数、去重、排序分页
- 原题:
- 重点:
先把员工行压缩成不同薪资等级,再把一基名次转换为零基偏移并保留 NULL 合同
题目重述¶
Employee(id, salary) 表保存员工及薪资。实现 MySQL 函数
getNthHighestSalary(N),返回第 N 高的 不同薪资值。
N 从 1 开始:N = 1 表示最高薪资。相同薪资只占一个名次;若不同薪资等级不足
N 个,函数返回 NULL。
自建示例¶
Employee:
id | salary
1 | 7200
2 | 5400
3 | 7200
4 | 4600
getNthHighestSalary(2) = 5400
getNthHighestSalary(4) = NULL
不同薪资降序为 7200、5400、4600;重复的 7200 只占第一个名次。
Employee:
id | salary
1 | 3000
2 | 3000
getNthHighestSalary(1) = 3000
getNthHighestSalary(2) = NULL
SQL 实现¶
CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
SET N = N - 1;
RETURN (
SELECT DISTINCT salary
FROM Employee
ORDER BY salary DESC
LIMIT N, 1
);
END
题解¶
原始行排名混入了重复员工¶
若直接按 salary DESC 排序员工行,第 N 行表示第 N 名员工,而不是第 N
个薪资等级。示例的前两行都可能是 7200,于是 N = 2 会错误返回最高薪资。
窗口函数也必须选择正确语义:直接对员工行使用 ROW_NUMBER 会给重复薪资不同序号;
RANK 会在重复组后留下名次空洞。可以使用 DENSE_RANK,但本题只需返回一个值,
先 DISTINCT 再定位更直接。
先压缩成真正的搜索序列¶
SELECT DISTINCT salary 把任意数量的员工行压缩为不同薪资等级。随后
ORDER BY salary DESC 将这些等级排列为题目定义的次序:
位置:1 2 3
薪资:7200 5400 4600
去重必须发生在取位置之前。若先限制员工行再去重,重复的高薪行可能占满窗口,使真正的
第 N 个等级从候选中消失。
一基名次到零基偏移¶
SQL LIMIT offset, row_count 的偏移从 0 开始,而函数参数 N 从 1 开始。因此进入
查询前执行 SET N = N - 1:
第 1 高 -> 跳过 0 行
第 2 高 -> 跳过 1 行
第 N 高 -> 跳过 N - 1 行
LIMIT N, 1 随后只读取目标位置的一行。先减一再传给 LIMIT 的顺序直接编码了两种
下标体系的转换;题目保证传入正整数,因此不会产生负偏移。
函数为何能返回 NULL¶
RETURN (...) 中的括号把查询作为标量子查询使用:
找到目标薪资时,子查询恰好返回一个值;
不同薪资不足
N个时,偏移后没有行,标量子查询的结果为NULL。
因此无需返回字符串 "NULL",也无需用 0 作为哨兵。0 可能是合法薪资,而 SQL 空值
正好表示“第 N 个等级不存在”。LIMIT 保证子查询最多一行,不会违反标量上下文。
具体走读¶
对 7200、5400、7200、4600 且 N = 2:
DISTINCT得到7200、5400、4600;降序排列后顺序不变;
函数把
N从 2 改为偏移 1,跳过 7200,读取一行 5400 并返回。
若 N = 4,跳过三个已有等级后没有剩余行,标量子查询返回 NULL。整个过程不会因
7200 对应两个员工而改变偏移量。
与固定第二高查询的关系¶
固定查询第二高时,可以把它写成“小于最高薪资的最大值”;推广到任意 N 后,反复
嵌套 MAX 会随 N 增加查询层数。去重、排序、偏移一次性建立完整的不同薪资顺序,
让 N 只影响跳过多少行,结构保持不变。
执行代价¶
逻辑工作包括去重、降序排序和读取一个偏移位置。无可用索引时,数据库通常需要扫描
Employee 并对不同薪资排序;设员工数为 m、不同薪资数为 u,排序上界为
O(u log u)。薪资索引、流式去重及优化器选择可能降低实际代价,但不会改变“先形成
不同等级,再按降序取零基偏移”的查询语义。