LeetCode 569. 员工薪水中位数
题目描述
题意分析
分别按公司查找薪水位于中间位置的员工记录。公司内先按
salary升序排列，同薪时按唯一的id升序打破并列；人数为奇数时返回中间一行，为偶数时返回中间两行，结果顺序不限。需要保留员工原始字段，因此应定位排序后的行，而不是把中间两个薪水求平均。先给每行标出公司内位置和公司总人数，再筛选中间位置即可。
解法：窗口函数定位中位数行
核心思路
[!blue]
为每行同时标上公司内行号和公司总人数。PARTITION BY company让每家公司独立计算。ROW_NUMBER按salary, id给每位员工分配从一开始的连续行号rn，重复薪水仍然占据不同位置；COUNT(*) OVER (PARTITION BY company)不按顺序累积，而是把公司总人数cnt写到该公司的每一行上。中间位置统一写成从
(cnt+1) DIV 2到(cnt+2) DIV 2，DIV表示整数除法。若cnt = 2m+1，两个边界都是m+1；若cnt = 2m，两个边界分别为m和m+1，恰好覆盖应返回的一行或两行。窗口函数保留每条员工记录，只增加辅助列。先在派生表中算好
rn、cnt，外层再过滤，就能按照完整公司的排序和人数取中位行；同层WHERE发生在窗口计算之前，不能直接用尚未生成的窗口结果筛选。
解题步骤
- 按公司分区，按薪水和 id 计算行号。
- 计算每个公司的完整人数。
- 外层筛选两个中位位置之间的行号。
- 只输出原员工字段。
代码实现
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+1))$，具体取决于索引与执行计划。
- 空间复杂度：窗口排序与中间结果通常按 $O(n)$ 估算。
关键点总结
[!green]
- 取的是位置上的记录，不是薪水平均值。
ROW_NUMBER直接表达员工行位置，同薪时按id排序是题目的要求。- 人数窗口需要整个分区总数。
解法二：自连接 + 条件聚合
核心思路
[!blue]
不直接生成排序行号，也可以计算每位员工前面有多少人。将员工
e与同公司的全部员工peer自连接，按salary, id比较，统计排在e前面的记录数less；COUNT(*)同时得到公司总人数cnt，所以e的行号就是less+1。中位行条件可以写成
cnt <= 2*(less+1) <= cnt+2，移项后得到cnt-2 <= 2*less <= cnt。因为less是整数，奇数人数时只能取一个值，偶数人数时能取两个相邻值，恰好对应应返回的中位行，无需分别讨论薪水是否相等。每个分组固定一位员工，连接得到该公司的全部同行，因此条件聚合恰好统计它在严格排序中的前驱数，筛选条件也就与窗口法相同。题面的进阶还提到不使用内置函数；这里仅去掉窗口函数，仍使用
SUM、COUNT聚合计数。
解题步骤
- 自连接同公司的员工，保留每位员工对应的全部同行。
- 按当前员工分组，用条件聚合统计按薪水、编号排在它前面的人数。
- 通过两倍前驱数与公司人数的关系，筛选中位行。
代码实现
SELECT e.id, e.company, e.salary
FROM Employee AS e
JOIN Employee AS peer
ON e.company = peer.company
GROUP BY e.id, e.company, e.salary
HAVING 2 * SUM(
CASE
WHEN peer.salary < e.salary
OR (peer.salary = e.salary AND peer.id < e.id)
THEN 1
ELSE 0
END
) BETWEEN COUNT(*) - 2 AND COUNT(*);
复杂度分析
- 时间复杂度：设各公司人数为 $n_c$，同公司自连接产生 $\sum_c n_c^2$ 对记录，最坏为 $O(n^2)$；具体执行代价还取决于连接、分组计划与索引。
- 空间复杂度：分组累计量按 $O(n)$ 计；若执行计划物化连接结果，中间存储可能达到 $O(n^2)$。
关键点总结
[!green]
- 同薪记录用
id比较先后，不能把所有相同薪水视作同一个位置。- 连接包含当前员工自己，它计入公司人数，但不会计入严格排在前面的人数。
- 自连接计数避免了窗口函数，但公司人数较多时连接规模会明显增大。
易错点总结
[!yellow]
- 使用普通除法保留小数：偶数人数时下界落在半整数上，会漏掉靠前的中位行。
- 只按薪水分档并把档位当员工位置：同薪多人的档位不能代替公司内逐行位置。
- 只取一个中间位置：偶数公司少一行。
- 将计数变为默认累计窗口：cnt 不再代表公司总人数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 185. 部门工资前三高的所有员工 | 困难 | 同样按组处理薪资，本题找中间行位置，重复薪水会占多个位置，不能照搬按不同工资值的密集排名。 |