题目描述

(通过次数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;
picture loss