一、问题描述

在数据库操作中，我们常常需要从多个表中提取特定信息以满足业务需求。本次我们面临的问题是，从Employee和Department两个表中找出每个部门中收入排名前三的员工。

表结构分析

Elmployee表

列名	类型	说明
id	int	主键
name	varchar	员工姓名
salary	int	员工薪资
departmentId	int	部门ID

Department表

列名	类型	说明
id	int	主键
name	varchar	部门名称

问题核心

本题的关键在于找出每个部门内薪资排名前三的员工。这意味着我们需要对员工数据按部门进行分组，然后在每个组内对薪资进行降序排名，最后筛选出排名在前三的员工，并将其与对应的部门名称关联起来展示。

二、解题思路剖析

1. 分组与排名

为了找出每个部门内薪资排名前三的员工，我们需要将员工数据按部门进行分组。在 SQL 中，我们可以使用窗口函数来实现这个功能。窗口函数可以在不改变表结构的情况下，对数据进行分组和排序，并为每个分组内的行生成排名。

2. 筛选排名前三的员工

在得到每个员工在其所在部门内的薪资排名后，我们需要筛选出排名小于等于 3 的员工，这些员工就是每个部门内薪资排名前三的员工。

3. 关联部门名称

最后，我们需要将筛选出的员工信息与Department表进行关联，以获取每个员工所在部门的名称。

三、SQL 代码实现

-- 使用 CTE 创建一个临时结果集 RankedEmployees
WITH RankedEmployees AS (
    -- 从 Employee 表中选择所需的列，并使用 DENSE_RANK 窗口函数生成排名
    SELECT
        e.id,
        e.name,
        e.salary,
        e.departmentId,
        -- 按部门 ID 进行分区，在每个分区内按薪资降序排列，并生成排名
        DENSE_RANK() OVER (PARTITION BY e.departmentId ORDER BY e.salary DESC) AS salary_rank
    FROM
        Employee e
)
-- 从 RankedEmployees 临时结果集和 Department 表中选择所需的列
SELECT
    d.name AS Department,
    re.name AS Employee,
    re.salary AS Salary
FROM
    RankedEmployees re
JOIN
    Department d ON re.departmentId = d.id
-- 筛选出排名小于等于 3 的员工
WHERE
    re.salary_rank <= 3;

四、代码详细解释

1. CTE（公共表表达式）部分

WITH RankedEmployees AS (
    SELECT
        e.id,
        e.name,
        e.salary,
        e.departmentId,
        DENSE_RANK() OVER (PARTITION BY e.departmentId ORDER BY e.salary DESC) AS salary_rank
    FROM
        Employee e
)

• CTE 名称：RankedEmployees 是我们创建的临时结果集的名称，它就像是一个临时表，存储了我们对员工数据进行处理后的结果。

• DENSE_RANK() 窗口函数：这是实现排名功能的关键。PARTITION BY e.departmentId 表示按部门 ID 对员工数据进行分组，每个部门形成一个独立的组。ORDER BY e.salary DESC 表示在每个组内按薪资降序排列。DENSE_RANK() 函数会为每个组内的员工生成一个排名，相同薪资的员工排名相同，且排名是连续的。例如，如果有两个员工薪资相同且都排第一，那么下一个薪资较低的员工排名为第二，而不是第三。

2. 主查询部分

SELECT
    d.name AS Department,
    re.name AS Employee,
    re.salary AS Salary
FROM
    RankedEmployees re
JOIN
    Department d ON re.departmentId = d.id
WHERE
    re.salary_rank <= 3;

• 连接操作：JOIN Department d ON re.departmentId = d.id 表示将 RankedEmployees 临时结果集和 Department 表按部门 ID 进行连接，这样我们就可以将员工信息与对应的部门名称关联起来。

• 筛选条件：WHERE re.salary_rank <= 3 用于筛选出排名小于等于 3 的员工，这些员工就是每个部门内薪资排名前三的员工。

五、复杂度分析

1. 时间复杂度

• 对于 CTE 部分，我们需要对 Employee 表进行一次全表扫描，时间复杂度为 (O(n))，其中 n 是 Employee 表的行数。
• 在主查询中，连接操作和筛选操作的时间复杂度主要取决于表的大小，由于我们已经对 Employee 表进行了预处理，连接和筛选的时间复杂度相对较低。总体来说，整个查询的时间复杂度为 (O(n))。

2. 空间复杂度

• CTE 创建的临时结果集 RankedEmployees 需要存储员工的基本信息和排名信息，其空间复杂度为 (O(n))，其中 n 是 Employee 表的行数。

六、测试用例验证

1. 输入数据

-- 插入 Employee 表数据
INSERT INTO Employee (id, name, salary, departmentId) VALUES
(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 表数据
INSERT INTO Department (id, name) VALUES
(1, 'IT'),
(2, 'Sales');

2. 预期输出

Department	Employee	Salary
IT	Max	90000
IT	Joe	85000
IT	Randy	85000
IT	Will	70000
Sales	Henry	80000
Sales	Sam	60000

3. 验证过程

将上述 SQL 代码在数据库中运行，将得到的结果与预期输出进行对比。如果结果一致，则说明我们的代码实现正确。

七、常见问题解答

1. 为什么使用 DENSE_RANK() 而不是 RANK() 或 ROW_NUMBER()？

• RANK() 函数在遇到相同值时会跳过后续的排名。例如，如果有两个员工薪资相同且都排第一，那么下一个薪资较低的员工排名为第三。

• ROW_NUMBER() 函数会为每个行分配一个唯一的排名，即使值相同也会有不同的排名。

• 而 DENSE_RANK() 函数在遇到相同值时会为它们分配相同的排名，且后续的排名是连续的，这符合我们本题中对排名的要求。

2. 如果部门员工数量少于 3 人会怎样？

如果某个部门的员工数量少于 3 人，那么该部门的所有员工都会被筛选出来，因为他们的排名都小于等于 3。

3. 如何修改代码以找出排名前 N 的员工？

如果要找出排名前 N 的员工，只需将 WHERE re.salary_rank <= 3 中的 3 替换为 N 即可。

感谢各位的阅读，后续将持续给大家讲解力扣中的算法题和数据库题，如果觉得这篇内容对你有帮助，别忘了点赞和关注，后续还有更多精彩的算法解析与你分享！