LeetCode 569. 员工薪水中位数

2020-11-09 HGNULB 约 9 分钟

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

分类

题目描述

✅ 569. 员工薪水中位数

题意分析

Employee 表里每行是一名员工，含 id、company、salary 三个字段。要求按公司分组，取出每家公司薪水处于中位数位置的那些员工记录，输出完整的行（id、company、salary），行序不限。

关键在于把「中位数」这个统计量精确翻译成「取第几行」。把某家公司的员工按薪水升序排好、从 1 开始编号，设人数为 cnt：cnt 为奇数时中位数只有一条，位于第 $(cnt + 1) / 2$ 行；cnt 为偶数时中位数是中间两条，位于第 $cnt/2$ 与第 $cnt/2 + 1$ 行。题目要的不是中位数的数值，而是处在那个位置上的原始记录，所以不能用 AVG 之类的聚合把两条压成一条。

这一点决定了整道题的结构：需要为每一行同时知道两个量——它在本公司内的排名，以及本公司一共有多少人。这两个量都是「相对于所在分组」的，但又必须保留在行级别上（不能把行聚合掉），这正是窗口函数的用武之地：OVER (PARTITION BY ...) 让每行都能看到自己所在分组的统计结果，同时行本身一条不少。

若不用窗口函数，就只能靠自连接计数（对每一行统计「本公司薪水比它低的人有几个」）来模拟排名，代价是 $O(n^2)$ 级别的连接，写起来也繁琐。约束里公司数与员工数都不大，两种写法都能过，但窗口函数是现代 SQL 面试的标准答案。

边界要留意几处：薪水可能重复（例如示例中公司 C 有两个 2645），排名必须用能产生连续且唯一序号的函数，否则并列会打乱行数与位置的对应关系；公司只有 1 人时中位数就是那一个人；公司人数为偶数时必须输出两条而不是一条。

解法：窗口函数定位中位数行

核心思路

先想清楚「难在哪」。中位数的定义依赖于排序后的位置，而 SQL 的表本身是无序集合；同时「第几位」是相对于所在公司的，而不是全表的。所以必须先在每个公司内部建立一套局部的、从 1 开始的序号。

ROW_NUMBER() OVER (PARTITION BY company ORDER BY salary, id) 恰好做这件事：PARTITION BY company 把数据按公司切成互不相干的窗口，ORDER BY salary 在窗口内按薪水升序，ROW_NUMBER() 依次赋予 1, 2, 3, ...。

排序键要追加 id 作为第二关键字，这一点很重要。薪水存在并列时，只写 ORDER BY salary 会让并列行的相对次序不确定——不同引擎、不同执行计划可能给出不同结果，导致同一份数据两次运行输出不同的行。加上唯一的 id 作为决胜键，排序就是全序，结果稳定可复现。这也是为什么不能用 RANK()：RANK() 遇到并列会给出相同名次并跳号（1, 2, 2, 4），序号既不唯一也不连续，与「第几行」的语义对不上。

同时还需要每家公司的总人数。COUNT(*) OVER (PARTITION BY company) 用同一套分区规则，把分组总数「广播」到该分组的每一行上——注意它没有 ORDER BY，所以统计的是整个分区而不是累计到当前行的部分。这就是窗口函数相对 GROUP BY 的核心优势：不损失行，却能拿到分组级别的聚合值。

有了 rn（行内排名）和 cnt（公司人数），中位数的位置就能统一成一个区间。奇偶两种情况可以合并成同一个式子：下界 $\lfloor (cnt + 1) / 2 \rfloor$，上界 $\lfloor (cnt + 2) / 2 \rfloor$（整数除法）。cnt 为奇数时两者相等，取一行；cnt 为偶数时上界比下界大 1，取两行。举例：cnt = 5 得区间 [3, 3]；cnt = 6 得区间 [3, 4]；cnt = 1 得 [1, 1]。一个 WHERE rn BETWEEN 下界 AND 上界 就把奇偶两种情况一网打尽，不需要 CASE WHEN。

这里必须用整数除法。MySQL 的 / 是浮点除法，(6 + 1) / 2 会得到 3.5 而不是 3，区间变成 [3.5, 4]，公司人数为偶数时只会返回一条记录——这是本题最隐蔽也最致命的坑。用 DIV 运算符（或 FLOOR(...)）显式表达整数除法，意图清晰且结果确定。

结构上，窗口函数不能直接写在 WHERE 里（WHERE 在窗口函数之前求值），所以必须先用子查询算出 rn 与 cnt，再在外层过滤。

解题步骤

在子查询中对 Employee 计算 ROW_NUMBER() OVER (PARTITION BY company ORDER BY salary, id) AS rn。为什么：中位数是位置概念，必须先在每家公司内部建立从 1 开始的连续序号；PARTITION BY company 保证不同公司互不干扰，ORDER BY salary 定义了「中间」的含义。

排序键追加 id。为什么：薪水可能并列，只按 salary 排序时并列行的先后由引擎自行决定，结果不可复现；id 唯一，追加后排序成为全序，任何执行计划下输出都一致。

用 ROW_NUMBER() 而不是 RANK() 或 DENSE_RANK()。为什么：只有 ROW_NUMBER() 给出唯一且连续的 1..cnt，与「第几行」严格一一对应；RANK() 并列时跳号、DENSE_RANK() 并列时重号，都会让位置与行数脱钩。

同一子查询中计算 COUNT(*) OVER (PARTITION BY company) AS cnt。为什么：判断中位数位置需要知道分组总数，而窗口版的 COUNT 能在不折叠行的前提下把总数带到每一行上；这里刻意不写 ORDER BY，否则会变成累计计数（等价于 rn），失去总数的含义。

把带 rn、cnt 的结果包成派生表。为什么：同层 WHERE 早于窗口结果产生，不能引用 rn、cnt；外层查询才能把它们当普通列过滤。

外层用 WHERE rn >= (cnt + 1) DIV 2 AND rn <= (cnt + 2) DIV 2 过滤。为什么：这一对边界把奇偶两种情形统一成一个区间——奇数时上下界重合取一行，偶数时相差 1 取两行，省掉了 CASE WHEN 分支。用 DIV 而不是 /，是因为 MySQL 的 / 返回小数，会把偶数情形的下界抬高半位、漏掉一条记录。

SELECT id, company, salary 输出原始字段。为什么：题目要的是完整的员工记录而不是中位数数值，所以既不能聚合也不能只输出薪水；rn 和 cnt 是中间产物，不应出现在结果里。

以示例数据走一遍。公司 A 有 6 人，薪水分别是 15, 341, 451, 513, 2341, 15314（对应 id 为 3, 2, 5, 6, 1, 4）；公司 B 有 6 人：13, 15, 234, 1154, 1221, 1345（id 为 8, 7, 12, 9, 11, 10）；公司 C 有 5 人：65, 2345, 2645, 2645, 2652（id 为 17, 13, 14, 15, 16）。

子查询为公司 A 的六行分别打上 rn = 1..6、cnt = 6。外层算出下界 (6 + 1) DIV 2 = 3、上界 (6 + 2) DIV 2 = 4，于是保留 rn = 3 与 rn = 4，即薪水 451（id 5）和 513（id 6）——恰好是六人排序后的中间两位。

公司 B 同样 cnt = 6，区间仍是 [3, 4]，保留薪水 234（id 12）和 1154（id 9）。

公司 C 的 cnt = 5，下界 (5 + 1) DIV 2 = 3、上界 (5 + 2) DIV 2 = 3，区间退化成 [3, 3]，只保留 rn = 3。这里正是并列发挥作用的地方：两个 2645 的 id 分别是 14 和 15，排序键的第二关键字 id 让 id = 14 稳定地排在第 3 位、id = 15 排在第 4 位，于是输出 id = 14。若只按 salary 排序，第 3 位是 14 还是 15 就成了随机结果。

最终输出五行：A 的 451、513，B 的 234、1154，C 的 2645（id 14）。

顺带看一眼那个整数除法的坑：若把 DIV 写成 MySQL 的 /，公司 A 的下界会变成 3.5，rn = 3 的那条被挡在外面，只输出 rn = 4 一条，六人公司的中位数凭空少了一半。

代码实现

SELECT id, company, salary
FROM (
    SELECT
        id,
        company,
        salary,
        -- 公司内按薪水升序编号；追加 id 作决胜键，保证并列时排序稳定。
        ROW_NUMBER() OVER (PARTITION BY company ORDER BY salary, id) AS rn,
        -- 不带 ORDER BY，统计的是整个分区的人数并广播到每一行。
        COUNT(*) OVER (PARTITION BY company) AS cnt
    FROM Employee
) AS ranked
-- DIV 是整数除法：奇数时上下界重合取一行，偶数时相差 1 取两行。
WHERE rn >= (cnt + 1) DIV 2
  AND rn <= (cnt + 2) DIV 2;

复杂度分析

时间复杂度：通常为 $O(n \log n)$，主要成本是按公司、薪水和 id 的窗口排序；排名、计数与外层过滤是线性扫描。实际代价由索引和执行计划决定。

空间复杂度：最坏 $O(n)$，用于窗口排序和执行缓冲；每家公司最终只输出一行或两行。

关键点总结

「取中位数所在的记录」和「算中位数的数值」是两回事。前者必须保留行，因此排除掉 GROUP BY + 聚合的思路，直接指向窗口函数。看清输出粒度是所有 SQL 题的第一步。

窗口函数的价值在于在不折叠行的前提下拿到分组级信息。凡是遇到「每行都要和自己所在分组的统计量做比较」的需求（排名、占比、与组内最大值的差），都该条件反射地想到 OVER (PARTITION BY ...)。

排名函数三选一要说得出理由：ROW_NUMBER() 唯一且连续、RANK() 并列跳号、DENSE_RANK() 并列不跳号。本题需要「第几行」，只有 ROW_NUMBER() 满足。这是排名类 SQL 面试的必考对比。

排序键要构造成全序。只要排序键有可能并列，就追加一个唯一列（通常是主键）兜底，否则结果不可复现——这在生产环境里是比「写错」更难排查的问题。

注意 SQL 方言的除法语义：MySQL 的 / 永远是浮点除法，要整数除法必须用 DIV 或 FLOOR。这个差异在跨库迁移时是高频事故源。

面试表达顺序应是：先把中位数化成行号区间，再说明 ROW_NUMBER 为什么必须按 (salary, id) 构造全序，最后解释奇偶人数如何由同一对边界覆盖。

易错点总结

用 / 而不是 DIV 做除法：公司人数为 6 → 下界算成 3.5，rn = 3 被过滤掉，只输出一条中位数记录，正确答案是两条。

用 RANK() 代替 ROW_NUMBER()：公司 C 有两个薪水 2645 → 它们同为第 3 名、下一名直接跳到 5，序号既不唯一也不连续，rn = 3 会匹配到两行，输出多出一条。

ORDER BY 只写 salary 不加 id：公司 C 的两个 2645 → 谁排第 3 位由引擎决定，同样的数据两次运行可能分别返回 id = 14 和 id = 15，判题随机失败。

COUNT(*) OVER (PARTITION BY company ORDER BY salary) 带上了 ORDER BY：窗口退化成「从分区首行累计到当前行」→ cnt 变成了和 rn 一样的递增值，过滤条件恒真或恒假，输出整表或空集。

把窗口函数直接写进 WHERE：WHERE ROW_NUMBER() OVER (...) = 1 → 语法错误，因为 WHERE 在窗口函数之前求值，必须下沉到子查询或 CTE。

用 GROUP BY company 配合 AVG(salary) 求中位数：偶数人数时两条中间记录被平均成一个数 → 输出的是数值而非原始记录，且 id 无从取值。

忘记 PARTITION BY company：ROW_NUMBER() 在全表范围内编号 → 只会产生一组全局中位数，多家公司的结果被合并成一条，其余公司全部丢失。

区间写成 rn = (cnt + 1) DIV 2：公司人数为 6 → 只取到 rn = 3，漏掉 rn = 4，偶数公司永远只返回一条。

区间写成 rn >= cnt DIV 2 AND rn <= cnt DIV 2 + 1：公司人数为 5 → 区间是 [2, 3]，取出两条，而奇数人数的中位数只应有一条。

在结果里保留 rn、cnt 列：输出列数与期望不符 → 判题直接判错，中间产物必须在外层 SELECT 中剔除。

相似题目

题目	难度	考察点
185. 部门工资前三高的所有员工	困难	同为分组内取排名靠前的记录，但要求「前三高的薪水」，需用 `DENSE_RANK()`
184. 部门工资最高的员工	中等	只取组内最大值，可用窗口函数也可用 `IN (SELECT MAX ...)` 子查询
178. 分数排名	中等	输出排名本身而非记录，并列必须同名次且不跳号，正好考 `DENSE_RANK()`
177. 第N高的薪水	中等	需要写成函数并处理「不存在第 N 高」时返回 `NULL` 的边界
176. 第二高的薪水	中等	177 的固定 N 版本，重点在去重与空结果的兜底写法
180. 连续出现的数字	中等	同样依赖行间顺序，但用 `LAG`/`LEAD` 看前后行而非分区内排名
295. 数据流的中位数	困难	同一统计量的算法版，数据动态到达，用对顶堆维持中位数而非排序定位
480. 滑动窗口中位数	困难	中位数需随窗口滑动增删元素，考的是可删除的对顶堆或有序集合