0177. Nth Highest Salary ======================== 题目信息 -------- :题号: 0177. 第 N 高的薪水 :难度: Medium :主题: Database、存储函数、去重、排序分页 :原题: `LeetCode 0177 `_ :重点: 先把员工行压缩成不同薪资等级,再把一基名次转换为零基偏移并保留 NULL 合同 题目重述 -------- ``Employee(id, salary)`` 表保存员工及薪资。实现 MySQL 函数 ``getNthHighestSalary(N)``,返回第 ``N`` 高的 **不同薪资值**。 ``N`` 从 1 开始:``N = 1`` 表示最高薪资。相同薪资只占一个名次;若不同薪资等级不足 ``N`` 个,函数返回 ``NULL``。 自建示例 -------- .. code-block:: text Employee: id | salary 1 | 7200 2 | 5400 3 | 7200 4 | 4600 getNthHighestSalary(2) = 5400 getNthHighestSalary(4) = NULL 不同薪资降序为 7200、5400、4600;重复的 7200 只占第一个名次。 .. code-block:: text Employee: id | salary 1 | 3000 2 | 3000 getNthHighestSalary(1) = 3000 getNthHighestSalary(2) = NULL SQL 实现 -------- .. code-block:: 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`` 将这些等级排列为题目定义的次序: .. code-block:: text 位置:1 2 3 薪资:7200 5400 4600 去重必须发生在取位置之前。若先限制员工行再去重,重复的高薪行可能占满窗口,使真正的 第 ``N`` 个等级从候选中消失。 一基名次到零基偏移 ~~~~~~~~~~~~~~~~~~ SQL ``LIMIT offset, row_count`` 的偏移从 0 开始,而函数参数 ``N`` 从 1 开始。因此进入 查询前执行 ``SET N = N - 1``: .. code-block:: text 第 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)``。薪资索引、流式去重及优化器选择可能降低实际代价,但不会改变“先形成 不同等级,再按降序取零基偏移”的查询语义。