MySQL中查询中位数？

导读

计算中位数可能是小学的内容，然而在数据库查询中实现却并不是一件容易的事。我们今天就来看看都有哪些方法可以实现。

注：本文所用MySQL版本无限制，所列题目均来源于LeetCode。

LeetCode数据库题目中关于中位数的主要有两道题，难度都是hard级别。两道题目无论是出现频率还是相关企业标签数，都属于比较靠前的位置，包括题解和讨论数量也是如此，足以见其热门程度。

569# 员工薪水中位数

题目描述：

预期答案：

解法1

既然是求解中位数，我们首先想到的是根据中位数的定义进行求解：奇数个数字时，中位数是中间的数字；偶数个数字时，中位数中间两个数的均值。本题不进行求解均值，而是将两个中位数全部显示。

根据定义，为了查询中位数，我们需要知道3点信息：

• 总数是奇数个还是偶数个
  

• 待查找数字总数

• 每个数字的排序编号

前两点信息在MySQL中非常简单，只需简单的count计数即可，而排序编号则需要借助辅助方法。在MySQL8.0以上版本引入了窗口函数后非常容易实现，但以前的版本则仅可通过自定义变量的方式获得排序值。这里如何对员工薪水进行分组排序不再展开，具体可参考历史文章一文解决所有MySQL分类排名问题。

在有了排名和数字总数之后，如何判断是中位数呢？这里计数字总数为N，则

• N为奇数，中位数排序编号是(N+1)/2=N/2+0.5

• N为偶数，中位数排序编号是N/2和N/2+1
  

进一步地，N为奇数和N为偶数是互斥的，求解出的中位数排序编号也是互斥的，也就是说3个排序编号不会同时取得整数，从而可以不加区分的直接判断即可。

查询SQL语句：

 1SELECT
 2    e1.Id, e1.Company, e1.Salary
 3FROM
 4    (SELECT Id, Company, Salary, @rnk:=if(@pre=Company, @rnk+1, 1) rnk, @pre:=Company
 5    FROM Employee, (SELECT @rnk:=0, @pre:=null)init
 6    ORDER by Company, Salary, Id)e1 
 7    JOIN 
 8    (SELECT Company, count(*) cnt FROM Employee GROUP by Company) e2
 9    using(Company)
10WHERE e1.rnk in (cnt/2+0.5, cnt/2, cnt/2+1)

查询效率：

解法2

除了根据中位数的排序编号来定位其位置，实际上还可以换种思路但仍然是在其排序编号上做文章：如果一个数是中位数，那么就意味着正序和逆序时其位置是一致的：更严谨的说，奇数个数字是正逆序排序一致，偶数个数字时，两中位数顺序要互换一下，也就是相差为1。进而，我们发现无论数字总数是奇数还是偶数，中位数的正逆排序相差要么为0，要么为1。根据这一性质，我们分别实现正逆两遍排序，然后判断数字的排序编号即可。

查询SQL语句：

 1SELECT
 2    e1.Id, e1.Company, e1.Salary
 3FROM
 4    (SELECT Id, Company, Salary, @rnk:=if(@pre=Company, @rnk+1, 1) rnk, @pre:=Company
 5    FROM Employee, (SELECT @rnk:=0, @pre:=null)init
 6    ORDER by Company, Salary, Id)e1 
 7    JOIN 
 8    (SELECT Id, Company, Salary, @rnk:=if(@pre=Company, @rnk+1, 1) rnk, @pre:=Company
 9    FROM Employee, (SELECT @rnk:=0, @pre:=null)init
10    ORDER by Company, Salary DESC, Id DESC)e2
11    on e1.Id=e2.Id
12WHERE abs(e1.rnk - e2.rnk)<=1

查询效率：

解法3

前2种解法都是根据中位数的定义在数字排序编号上作文章，下面是一个对中位数性质更深的理解（摘抄自官方题解）

根据定义，我们来找一下 [1, 3, 2] 的中位数。首先 1 不是中位数，因为这个数组有三个元素，却有两个元素 (3，2) 大于 1。3 也不是中位数，因为有两个元素小于 3。对于 2 来说，大于 2 和 小于 2 的元素数量是相等的，因此 2 是当前数组的中位数。当数组长度为 偶数，且元素唯一时，中位数等于排序后 中间两个数 的平均值。对这两个数来说，大于当前数的数值个数跟小于当前数的数值个数绝对值之差为 1，恰好等于这个数出现的频率。 

结论：不管数组长度是奇是偶，也不管元素是否唯一，中位数出现的频率一定大于等于 大于它的数 和 小于它的数 的绝对值之差。

好吧，力扣的官方题解读起来总是这么生涩。不过细品之下，我们还是可以发现这个结论是对的。【好像说了句废话】

根据中位数的这一性质，可以写出如下查询语句：

 1SELECT
 2    e1.Id, e1.Company, e1.Salary
 3FROM
 4    Employee e1,
 5    Employee e2
 6WHERE
 7    e1.Company = e2.Company
 8GROUP BY e1.Company , e1.Salary
 9HAVING SUM(e1.Salary = e2.Salary) >= ABS(SUM(SIGN(e1.Salary - e2.Salary)))
10ORDER BY e1.Id

查询效率：

实际上，虽然3种解法均为两表关联，但由于解法3中涉及到相对更为复杂的计算，其效率竟然要比解法1和解法2中低太多。

所以，不妨想想奥卡姆剃刀原理，大道至简、大巧不工、简单之美！

---

571# 给定数字的频率查询中位数

刚才一道题是对给定的一组数字查询中位数，顶多也就是要进行分组后查询中位数。那如果给定的数字不是数字全样本，而是数字+频率呢？

题目描述：

注：与前一题不同，本题中如果中位数有两个，返回的是一个均值。

解法1

这一题乍一看还是挺懵的，但有了第一题解法3中的结论，似乎它就是为这一题做的铺垫：这不刚好就是提供的数字及其频率吗？对比其小的数字频率求和就是比其小的数字个数，类似的也可以得到比其大的数字个数。

这样的想法其实非常适合窗口函数，如果是在8.0以上版本，那么如下SQL语句可谓是简洁优雅：

 1SELECT
 2    number 
 3FROM
 4    (SELECT number, Frequency,
 5            sum( Frequency ) over (rows BETWEEN unbounded preceding AND current ROW ) cnt1,
 6            sum( Frequency ) over (rows BETWEEN current ROW AND unbounded following ) cnt2 
 7    FROM
 8        numbers ) tmp 
 9WHERE
10    Frequency >= abs(cnt2 - cnt1)

其中：cnt1为当前行之前的累计个数（含当前行），cnt2为当前行之后的累计个数（含当前行），进而cnt2-cnt1等于比其大的数字和比其小的数字个数之差。

当然，当前LeetCode OJ是5.6版本，MySQL也不能使用窗口函数。此时，可以简单的通过自定义变量得到实现：

1SELECT 
2    avg(number) median
3FROM
4    (SELECT number, Frequency, @cnt:=@cnt+Frequency cnt
5    FROM numbers, (SELECT @cnt:=0)init
6    ORDER BY number)tmp1,
7    (SELECT sum(Frequency) total FROM numbers)tmp2
8WHERE
9    Frequency>=abs(total-2*cnt+Frequency)

类似的，这里：

• cnt为当前行之前的累计数字个数（含当前行），cnt-Frequency为不含当前行的数字个数

• total为总的数字个数，total-cnt即为当前行之后的数字个数（不含当前行）
  

• total-cnt - cnt+Frequency即为需要求的差值
  

查询效率：

解法2

前面的方法是借助了中位数的一个性质，实话说还是不够直观。那么，如果仍然沿用中位数排序编号的规律，是否可以用于本题的SQL查询呢？

当然可以。实际上，根据数字及频率，可以稍微变形得到数字排序编号的首末区间，然后判断中位数的编号存在于哪个数字的首末区间即可找到中位数。

带着这一想法，我们首先写出如下SQL语句来获得数字的首末区间：

1SELECT 
2    number, frequency, @beg:=@end+1 AS beg, @end:=@beg+frequency-1 AS end 
3FROM 
4    numbers, (SELECT @beg := 0, @end :=0) init 
5ORDER BY
6    number 

得到如下中间结果：

然后，对中位数位置的三个可能取值（即N/2, N/2+0.5, N/2+1）分别判断是否存在首末区间，进而判断是否是中位数：

 1SELECT 
 2    avg(number) median 
 3FROM
 4    ( SELECT 
 5            number, frequency,  @beg := @end+1 AS beg,  @end := @beg+frequency-1 AS end 
 6        FROM 
 7            numbers, (SELECT @beg := 0, @end :=0) init 
 8        ORDER BY
 9            number 
10    ) t1,
11    ( SELECT sum(frequency) cnt FROM numbers ) t2 
12WHERE
13    (cnt/2 BETWEEN beg AND end)
14    or (cnt/2+0.5 BETWEEN beg AND end)
15    or (cnt/2+1 BETWEEN beg AND end)

查询效率：

解法3

利用中位数的排序值可以判断，利用正逆序的差值应该也可以。仍然是通过正逆两遍排序得到每个数字的两组首末区间，然后判断两个区间在相差1范围内是否存在交集即可。

查询SQL语句：

 1SELECT 
 2    avg(number) median
 3FROM
 4    ( SELECT 
 5            number, frequency,  @beg1 := @end1+1 AS beg,    @end1 := @beg1+frequency-1 AS end 
 6        FROM 
 7            numbers, (SELECT @beg1 := 0, @end1 :=0) init 
 8        ORDER BY
 9            number 
10    ) t1
11    JOIN
12    ( SELECT 
13            number, frequency,  @beg2 := @end2+1 AS beg,    @end2 := @beg2+frequency-1 AS end 
14        FROM 
15            numbers, (SELECT @beg2 := 0, @end2 :=0) init 
16        ORDER BY
17            number desc
18    ) t2
19    using(number)
20WHERE
21    t1.beg BETWEEN t2.beg-1 and t2.end+1 or t1.end BETWEEN t2.beg-1 and t2.end+1

查询效率：

我们发现，虽然解法3写起来相对复杂，但效率居然是最高的。不过个人还是比较喜欢解法2，即简单的根据中位数排序编号来判断，简单高效易懂。

---

以上就是LeetCode中两道关于中位数题目的几种解法，当然，肯定还有更多更好的解法，这里也只是简单探讨以作抛砖引玉。

相关阅读：