LeetCode：Department Top Three Salaries -各部门工资最高的三人

1、题目名称

Department Top Three Salaries（各部门工资最高的三个人）

2、题目地址

https://leetcode.com/problems/department-top-three-salaries/

3、题目内容

表Employee保存了所有雇员的数据，每名雇员都有一个Id，和一个部门Id（DepartmentId）

+----+-------+--------+--------------+
| Id | Name  | Salary | DepartmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
| 5  | Janet | 69000  | 1            |
| 6  | Randy | 85000  | 1            |
+----+-------+--------+--------------+

表Department保存了每个部门的Id和名称

+----+----------+
| Id | Name     |
+----+----------+
| 1  | IT       |
| 2  | Sales    |
+----+----------+

现需要写一个SQL，找出每个部门工资最高的三名雇员。例如以上面的两张表的数据，查询出的结果集应该是这样的：

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| IT         | Randy    | 85000  |
| IT         | Joe      | 70000  |
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+

4、初始化数据库脚本

在MySQL数据库中建立一个名为LEETCODE的数据库，用MySQL命令行中的source命令执行下面脚本：

-- 执行脚本前必须建立名为LEETCODE的DATABASE
USE LEETCODE;

DROP TABLE IF EXISTS Employee;
CREATE TABLE Employee (
  Id INT NOT NULL PRIMARY KEY,
  Name VARCHAR(10),
  Salary INT,
  DepartmentId INT
);

INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (1, 'JID', 70000, 1);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (2, 'KAT', 80000, 2);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (3, 'FCK', 60000, 2);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (4, 'DIR', 90000, 1);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (5, 'CAT', 69000, 1);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (6, 'DOT', 85000, 1);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (7, 'GOS', 25000, 1);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (8, 'OPA', 90000, 2);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (9, 'OPB', 30000, 2);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (10, 'DIK', 30000, 3);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (11, 'POD', 30000, 3);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (12, 'SUV', 30000, 3);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (13, 'ABC', 30000, 3);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (15, 'WKK', 75000, 4);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (16, 'JYY', 60000, 4);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (17, 'XWY', 60000, 4);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (18, 'KMT', 55000, 4);
INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES (14, 'LXK', 90000, 999);

DROP TABLE IF EXISTS Department;
CREATE TABLE Department (
  Id INT NOT NULL PRIMARY KEY,
  Name VARCHAR(10)
);

INSERT INTO Department (Id, Name) VALUES (1, 'DPRT1');
INSERT INTO Department (Id, Name) VALUES (2, 'DPRT2');
INSERT INTO Department (Id, Name) VALUES (3, 'DPRT3');
INSERT INTO Department (Id, Name) VALUES (4, 'DPRT4');

5、解题SQL

先写一个SQL，查询出每个有部门的人的部门和工资

SELECT D.NAME Dep, E.NAME Emp, E.Salary Sal
FROM Employee E
LEFT JOIN Department D ON E.DepartmentId = D.Id
WHERE D.NAME IS NOT NULL
使用 MySQL Query Browser 工具查询结果如下：

根据这个SQL，可以继续写出一个查询出每个部门工资处于前三名位置的员工列表：

SELECT A.Dep Department, A.Emp Employee, A.Sal Salary
FROM   (SELECT D.NAME Dep, E.NAME Emp, E.Salary Sal
        FROM   Employee E
        LEFT   JOIN Department D ON E.DepartmentId = D.Id
        WHERE  D.NAME IS NOT NULL) A
WHERE  (SELECT COUNT(*)
        FROM   (SELECT D.NAME Dep, E.NAME Emp, E.Salary Sal
                FROM   Employee E
                LEFT   JOIN Department D ON E.DepartmentId = D.Id
                WHERE  D.NAME IS NOT NULL) B
        WHERE  A.Dep = B.Dep AND
               A.Sal < B.Sal) < 3
ORDER  BY A.Dep ASC, A.Sal DESC

这个SQL的查询结果集如下：

可以看到，部门4（DPRT4）有四个人，一个高工资（WKK，75000），一个低工资（KMT，55000），其他两个人工资（JYY，XWY，60000）是一样的。按照上面的SQL，会查出该部门工资最高的三个人是WKK、JYY、XWY，我认为这是一种合理的结果，即：

查出每个部门工资排名最靠前的三个人，如有多于三人工资并列第一则将这些人都查出，如有多于两人工资并列第二则查出排名第一的人和这些并列第二的人，如有多于一人工资并列第三则查出排名第一、二名的人和所有并列第三名的人。

但这种类似计算长跑比赛前三名的算法却并不是本题的“正确答案”，本题实际上要我们找的并不是要你求出每个部门工资最高的三个人，而是要：

先求出每个部门第三高的工资，再求出该部门工资数不小于第三高工资的所有雇员。

虽然我认为这是不合理的答案，不过还是写了一个“正确”的SQL如下：

SELECT A.Dep Department, A.Emp Employee, A.Sal Salary
FROM   (SELECT D.NAME Dep, E.NAME Emp, E.Salary Sal
        FROM   Employee E
        LEFT   JOIN Department D ON E.DepartmentId = D.Id
        WHERE  D.NAME IS NOT NULL) A
WHERE  (SELECT COUNT(DISTINCT Sal)
        FROM   (SELECT D.NAME Dep, E.NAME Emp, E.Salary Sal
                FROM   Employee E
                LEFT   JOIN Department D ON E.DepartmentId = D.Id
                WHERE  D.NAME IS NOT NULL) B
        WHERE  A.Dep = B.Dep AND
               A.Sal < B.Sal) < 3
ORDER  BY A.Dep ASC, A.Sal DESC

查询出的结果集如下：

另一种更简单的SQL写法如下，查询结果集与上同：

SELECT D.NAME Department, E.NAME Employee, E.Salary Salary
FROM   Department D, Employee E
WHERE  E.DepartmentId = D.Id AND
       (SELECT COUNT(DISTINCT Salary)
        FROM   Employee
        WHERE  DepartmentId = D.Id AND
               Salary > E.Salary) < 3
END