江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第185题：部门工资前三高的所有员工

表: Employee +--------------+---------+ | Column Name | Type | +--------------+---------+ | id | int | | name | varchar | | salary | int | | departmentId | int | +--------------+---

题目描述

表: Employee

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| id           | int     |
| name         | varchar |
| salary       | int     |
| departmentId | int     |
+--------------+---------+
Id是该表的主键列。
departmentId是Department表中ID的外键。
该表的每一行都表示员工的ID、姓名和工资。它还包含了他们部门的ID。

表: Department

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| name        | varchar |
+-------------+---------+
Id是该表的主键列。
该表的每一行表示部门ID和部门名称。

公司的主管们感兴趣的是公司每个部门中谁赚的钱最多。一个部门的 高收入者 是指一个员工的工资在该部门的 不同 工资中 排名前三 的员工。

编写一个SQL查询，找出每个部门中收入高的员工。

以 任意顺序 返回结果表。

难度

困难

题目链接

点击在LeetCode中查看题目

示例

示例 1:

输入: 
Employee 表:
+----+-------+--------+--------------+
| id | name  | salary | departmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 85000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
| 5  | Janet | 69000  | 1            |
| 6  | Randy | 85000  | 1            |
| 7  | Will  | 70000  | 1            |
+----+-------+--------+--------------+
Department  表:
+----+-------+
| id | name  |
+----+-------+
| 1  | IT    |
| 2  | Sales |
+----+-------+
输出: 
+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| IT         | Joe      | 85000  |
| IT         | Randy    | 85000  |
| IT         | Will     | 70000  |
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+
解释:
在IT部门:
- Max的工资最高
- 随后是Joe和Randy，他们的工资相同
- Will的工资排第三。

在Sales部门:
- Henry的工资最高
- Sam的工资排第二
- 没有第三高的工资，因为只有两名员工。

提示

  • 该题目中，如果某个部门有两名或多名员工的工资相同，那么他们的排名应该相同。
  • 工资相同的员工，他们的排名并列。例如，如果有两名员工工资排名第二，那么下一个工资最高的员工的排名是第三。

解题思路

方法一：使用窗口函数 DENSE_RANK()

解决这道题目的关键是计算每个部门内员工工资的排名。我们可以使用窗口函数 DENSE_RANK() 对每个部门的员工按工资降序排名，然后筛选出排名前三的员工。

关键点：

  1. 使用窗口函数 DENSE_RANK() OVER(PARTITION BY departmentId ORDER BY salary DESC) 计算每个部门内员工工资的排名
  2. 将员工表与部门表连接
  3. 筛选出排名小于等于3的员工

时间复杂度：O(n log n)，其中 n 是 Employee 表中的行数（排序的时间复杂度） 空间复杂度：O(n)

方法二：使用相关子查询

另一种解决方法是使用相关子查询，对于每个员工，计算在同一部门中工资比他高的不同工资数量，如果这个数量小于3，则该员工是部门的高收入者。

关键点：

  1. 使用相关子查询计算每个员工在本部门中工资比他高的不同工资数量
  2. 筛选出这个数量小于3的员工
  3. 将结果与部门表连接获取部门名称

时间复杂度：O(n²)，其中 n 是 Employee 表中的行数 空间复杂度：O(n)

方法三：使用 JOIN 实现

也可以使用 JOIN 来实现类似的逻辑，对于每个员工，找出同一部门中工资比他高的不同员工数量。

关键点：

  1. 使用自连接找出同一部门中工资比当前员工高的员工
  2. 对这些员工的工资去重并计数
  3. 筛选出计数小于3的员工

时间复杂度：O(n²)，其中 n 是 Employee 表中的行数 空间复杂度：O(n)

代码实现

SQL 实现（方法一：窗口函数 DENSE_RANK()）

SELECT 
    d.name AS Department,
    e.name AS Employee,
    e.salary AS Salary
FROM 
    (
        SELECT 
            departmentId,
            name,
            salary,
            DENSE_RANK() OVER (PARTITION BY departmentId ORDER BY salary DESC) AS rnk
        FROM 
            Employee
    ) e
JOIN 
    Department d ON e.departmentId = d.id
WHERE 
    e.rnk <= 3;

SQL 实现（方法二：相关子查询）

SELECT 
    d.name AS Department,
    e.name AS Employee,
    e.salary AS Salary
FROM 
    Employee e
JOIN 
    Department d ON e.departmentId = d.id
WHERE 
    (
        SELECT COUNT(DISTINCT e2.salary)
        FROM 
            Employee e2
        WHERE 
            e2.departmentId = e.departmentId AND e2.salary > e.salary
    ) < 3;

SQL 实现（方法三：JOIN 实现）

SELECT 
    d.name AS Department,
    e1.name AS Employee,
    e1.salary AS Salary
FROM 
    Employee e1
JOIN 
    Department d ON e1.departmentId = d.id
WHERE 
    3 > (
        SELECT 
            COUNT(DISTINCT e2.salary)
        FROM 
            Employee e2
        WHERE 
            e2.departmentId = e1.departmentId AND e2.salary > e1.salary
    );

性能分析

各SQL实现的性能对比：

实现方法 执行用时 内存消耗 特点
方法一 507 ms 0B 使用窗口函数，代码简洁，性能较好
方法二 728 ms 0B 使用相关子查询，思路直观
方法三 735 ms 0B 使用JOIN和子查询，逻辑清晰

补充说明

代码亮点

  1. 方法一使用窗口函数 DENSE_RANK()，代码简洁高效
  2. 方法二和方法三使用子查询，思路直观易懂
  3. 所有方法都考虑了工资相同时排名并列的情况

关于窗口函数

SQL窗口函数是处理排名和分析问题的强大工具：

DENSE_RANK() 与 RANK() 的区别：

  • DENSE_RANK() 在排名中不会跳过重复的排名
  • RANK() 会在重复的排名后跳过相应数量的排名

例如，对于薪水序列 [100, 90, 90, 80]：

  • 使用 DENSE_RANK()，排名为 [1, 2, 2, 3]
  • 使用 RANK()，排名为 [1, 2, 2, 4]

对于本题，由于我们需要找出前三高的工资，且工资相同的员工排名应该相同，因此应使用 DENSE_RANK()。

方法比较

不同方法各有优缺点：

窗口函数：

  • 代码最简洁，易于理解
  • 性能通常最好，特别是对大型表
  • 不是所有数据库都支持窗口函数

相关子查询：

  • 思路直观，逻辑清晰
  • 在某些情况下性能可能较差，特别是对大型表
  • 几乎所有关系型数据库都支持

JOIN 实现：

  • 逻辑清晰，思路直观
  • 性能通常较差，特别是对大型表
  • 对于复杂查询，代码可能较冗长

对于本题，窗口函数方法通常是最佳选择，因为它既简洁又高效。

常见错误

  1. 使用 RANK() 而不是 DENSE_RANK()，导致排名跳跃
  2. 没有正确处理工资相同的情况
  3. 没有正确使用 DISTINCT 去除重复工资
  4. 没有正确连接 Department 表获取部门名称

相关题目