569. 员工薪水中位数（难度：困难）

题目描述

（通过次数16,611 | 提交次数29,027，通过率57.23%）

表: Employee
+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| id           | int     |
| company      | varchar |
| salary       | int     |
+--------------+---------+
Id是该表的主键列。
该表的每一行表示公司和一名员工的工资。

写一个SQL查询，找出每个公司的工资中位数。
以 任意顺序 返回结果表。

查询结果格式如下所示。
示例 1:
输入: 
Employee 表:
+----+---------+--------+
| id | company | salary |
+----+---------+--------+
| 1  | A       | 2341   |
| 2  | A       | 341    |
| 3  | A       | 15     |
| 4  | A       | 15314  |
| 5  | A       | 451    |
| 6  | A       | 513    |
| 7  | B       | 15     |
| 8  | B       | 13     |
| 9  | B       | 1154   |
| 10 | B       | 1345   |
| 11 | B       | 1221   |
| 12 | B       | 234    |
| 13 | C       | 2345   |
| 14 | C       | 2645   |
| 15 | C       | 2645   |
| 16 | C       | 2652   |
| 17 | C       | 65     |
+----+---------+--------+
输出: 
+----+---------+--------+
| id | company | salary |
+----+---------+--------+
| 5  | A       | 451    |
| 6  | A       | 513    |
| 12 | B       | 234    |
| 9  | B       | 1154   |
| 14 | C       | 2645   |
+----+---------+--------+

进阶: 你能在不使用任何内置函数或窗口函数的情况下解决它吗?

//测试数据
Create table If Not Exists Employee (id int, company varchar(255), salary int);

insert into Employee (id, company, salary) values ('1', 'A', '2341');
insert into Employee (id, company, salary) values ('2', 'A', '341');
insert into Employee (id, company, salary) values ('3', 'A', '15');
insert into Employee (id, company, salary) values ('4', 'A', '15314');
insert into Employee (id, company, salary) values ('5', 'A', '451');
insert into Employee (id, company, salary) values ('6', 'A', '513');
insert into Employee (id, company, salary) values ('7', 'B', '15');
insert into Employee (id, company, salary) values ('8', 'B', '13');
insert into Employee (id, company, salary) values ('9', 'B', '1154');
insert into Employee (id, company, salary) values ('10', 'B', '1345');
insert into Employee (id, company, salary) values ('11', 'B', '1221');
insert into Employee (id, company, salary) values ('12', 'B', '234');
insert into Employee (id, company, salary) values ('13', 'C', '2345');
insert into Employee (id, company, salary) values ('14', 'C', '2645');
insert into Employee (id, company, salary) values ('15', 'C', '2645');
insert into Employee (id, company, salary) values ('16', 'C', '2652');
insert into Employee (id, company, salary) values ('17', 'C', '65');

解题思路

这是一道典型求中位数的题目。也是一道困难题。

在解题之前，首先需要弄明白，中位数是什么意思。也就是说要搞懂业务需求，明白题目要求我们做什么。

不过，搞懂业务需求这件小事，很多时候，是说起来容易，做起来难。

我们知道，一个人的认知，有四个层次：

* ** 一、不知道自己不知道 **

* ** 二、知道自己不知道 **

* ** 三、知道自己知道 **

* ** 四、不知道自己知道 **

在面对一个问题时，很多人以为自己在第三层，而实际上，很可能是在第一层。

从第一层提升到第三层，是最难的，因为你很难向一个人解释清楚他不知道的东西。所谓“夏虫不可语冰”，正是这个道理。

而从第二层提升到第三层，相对来说就容易的多。这就是我们常说的，“当你知道问题是什么的时候，问题就解决了一半”。

那么，我们现在来看一下中位数的数学定义：

** 给定一个长度为n的数列，从小到大排序： **

** 如果n为偶数，则序号为n/2和n/2+1的值为中位数； **

** 如果n为奇数，则序号为(n+1)/2的值为中位数； **

上面定义中的排序，没有说明是升序，还是降序。既然如此，如果一个值是一个数列的中位数，那么它应该满足，不管是按升序来看，还是按降序来看，它都应该是这个数列的中位数。这也是中位数的一个特点。

基于中位数的数学定义，通过SQL实现的话，如果使用开窗函数，可以按如下步骤计算：

** 第一步 **，先计算出列表的长度（在这里，就是每个公司的总员工数）。

** 第二步 **，再计算出每个公司内，每个员工的薪水排名。

** 第三步 **，根据中位数的数学定义（数列的长度n，与值的序号的关系）来判断中位数。

如果不使用开窗函数呢？想一想怎么实现？

实际上，我们可以基于中位数的特点来实现。即：如果一个值是一个数列的中位数，那么，不管是升序还是降序，它都应该是这个数列的中位数。也就是说，数列中比它大的值的个数和比它小的值的个数，应该是相等的，或者是相差1个。

不过，这种方法，有一个局限性。

在数列中没有重复数据时，很容易计算。但如果数列中有重复数据，计算结果就可能出现偏差。比如本题中的样例数据，同一个公司，就存在两个以上的人有相同的薪水。

思考一下，这种情况可以怎么处理？

参考SQL

未特别说明的情况下，参考SQL为基于MySQL8.0实现。

with
tmpa as (
    select
        a.id,a.company,a.salary,count(1) cnt
    from Employee a
    inner join Employee b
    on a.company = b.company
    and (a.salary < b.salary
    or (a.salary = b.salary and a.id <= b.id)
    )
    group by a.id,a.company,a.salary
),
tmpb as (
    select
        a.id,a.company,a.salary,count(1) cnt
    from Employee a
    inner join Employee b
    on a.company = b.company
    and (a.salary > b.salary
    or (a.salary = b.salary and a.id >= b.id)
    )
    group by a.id,a.company,a.salary
)
select a.id,a.company,a.salary
from tmpa a
inner join tmpb b
on a.id = b.id
and abs(a.cnt-b.cnt)<=1;