第二高的薪水

题目

编写一个 SQL 查询，获取`Employee``表中第二高的薪水（Salary） 。

+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+

例如上述Employee表，SQL查询应该返回200作为第二高的薪水。如果不存在第二高的薪水，那么查询应返回null。

+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+

排序

先Employee表中的数据在列Salary上去重排序，然后，选取第二位的值即为第二高的薪水。

代码实现

MySQL版：

SELECT e.Salary AS SecondHighestSalary from (
SELECT DISTINCT Salary FROM Employee  
UNION ALL 
SELECT null FROM dual 
UNION ALL 
SELECT null FROM dual 
ORDER BY Salary DESC
) e LIMIT 1,1;

为了处理Employee表不包含任何记录或只包含一条记录的情况，UNION ALL了两条为null的记录。当表Employee为空或仅有一条记录时，LIMIT 1,1就会选中两条null记录中的一条。使用UNION ALL而不是UNION是为了避免去除重复。

复杂度分析

时间复杂度

当对无索引的字段排序时，MySQL使用filesort排序。假如待排序的数据量不大，足以全部加载进内存，则filesort相当于合併排序，时间复杂度为$\mathcal{O}(n \log n)$。

去重DISTINCT可在排序的同时完成。

所以，整体时间复杂度为$!mathcal{O}(n \log n)$。

空间复杂度

合併排序的空间复杂度为$\mathcal{O}(n)$，所以整体空间复杂度也为$\mathcal{O}(n)$。

两次遍历

第二高的薪水等于不包含第一高薪水的集合中最高的薪水。可以先一次遍历获取第一高的薪水。再第二次遍历，排除和第一高薪水相同的薪水，从剩余薪水中获取最高的即为全局第二高的薪水。

代码实现

MySQL版本：

SELECT MAX(e.Salary) AS SecondHighestSalary FROM (
    SELECT Salary FROM Employee 
    WHERE Salary < (
        SELECT IFNULL(MAX(Salary),0) FROM Employee
    )
    UNION ALL 
    SELECT null AS Salary FROM dual 
) e 
;

使用内建函数IFNULL将null值转换为0，应付表Employee为空的情形。再UNION ALL一个nullSalary，以应付Employee仅有一条记录的情形。

复杂度分析

时间复杂度

假设数据量为$n$，两次遍历时间复杂度为$\mathcal{O}(n)$。

空间复杂度

只在用了一个额外空间-最高薪水，空间复杂度为$\mathcal{O}(1)$。