专栏首页SQL实现SQL 计算中位数

SQL 计算中位数

笔者在 HackerRank 上的 SQL 编程挑战看到这题,这题有 96% 的提交成功率。实际上,使用 SQL 求中位数远远没那么简单。

问题描述

我们先来看关于“中位数”的解释:

❝中位数(Median)又称中值,统计学中的专有名词,是按顺序排列的一组数据中居于中间位置的数,代表一个样本、种群或概率分布中的一个数值,其可将数值集合划分为相等的上下两部分。对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。 ❞

再来看几个具体的例子:

  1. 对于 “1,2,3,4,5” ,总共有 5 个数,居中的数是 3 ,因此这组数据的中位数是 3 。
  2. 对于“1,2,3,4,5,6”,共有 6 个数,居中的是 3 和 4,因此这组数的中位数是 3 和 4 的平均数 3.5 。
  3. 对于“3,3,3,3,100,100,100”,总共有 7 个数,居中的是 3,因此 3 是这组数据的中位数。

解决方案

解决方案主要有两种,第一种方案是对数据按大小排序后找到居中的值,再求值的平均数;第二种解决方案计算出每个数与其它数的相对距离(两数相减,结果为正则作 1,结果为负作 0,相等是 0),再对位移的结果加和,通常得到最小的加和结果的数就在居中的位置。

先来看比较简单的解决方案,也就是第一种。具体的做法是:

  1. 对给定的一组数据按从小到大排序;
  2. 对排序后的数据编号,序号从 1 开始;
  3. 假设这组数据的总数是 N,若 N 是奇数,则居中的数的序号是 + 1;若 N 是偶数,则居中的数的序号是 N/2 和 + 1 。

注: 表示对 N/2 的结果向下取整。

对应的 SQL 实现:

# 准备数据
WITH t AS
(SELECT 3 AS num
 UNION ALL
SELECT 6
 UNION ALL
SELECT 3
 UNION ALL
SELECT 2
 UNION ALL
SELECT 5
 UNION ALL
SELECT 7),
t1 AS
(SELECT
  num,
  row_number () over (
ORDER BY num) AS rn,
COUNT(*) over () AS total
FROM
  t
ORDER BY num)
SELECT
  AVG(num)
FROM
  t1
WHERE rn IN (
    FLOOR(total / 2) + 1,
    IF(
      total % 2 = 0,
      FLOOR(total / 2),
      FLOOR(total / 2) + 1
    )
  )

只需要注意,在生成编号前先对原数据做排序,不然结果很可能就是错的。

我们再来看第二种解决方案。

如果事先没有对数据做排序处理,怎么知道一个数是否处于在一堆数的中间位置呢?

在数据没有出现重复的情况下,依次从这组数中取出一个数,和剩下的数做比较,如果该数大于要比较的数,则计为 1,反之为 0,再把比较的结果加和(把这个结果称作“margin”)。有多少个数,就有多少个加和的结果,加和的结果最小的数就是居中的数。

比如“1,2,3,5,6,7”这组数据,计算 margin,结果如下:

   num  margin  
------  --------
     1  5       
     2  3       
     3  1       
     5  1       
     6  3       
     7  5      

3 和 5 对应的加和结果最小,因此它们是居中的数。

如果数据有重复,就不能只使用上面的方法处理,还得加一些限制条件。这个限制条件就是统计该数与原数据相等的数的个数(统计的结果称作“equal”),只选出相等的个数大于或等于加和结果的数。

比如“3,3,3,5,7,7”这组数据,结算 equal 和 margin 的值,得到:

   num  equal   margin  
------  ------  --------
     3  3       3       
     5  1       1       
     7  2       4       

最终实现的 SQL 如下:

WITH t AS
(SELECT 3 AS num
 UNION ALL
SELECT 6
 UNION ALL
SELECT 3
 UNION ALL
SELECT 2
 UNION ALL
SELECT 5
 UNION ALL
SELECT 7),
t1 AS
(SELECT
  a.num,
  SUM(IF(a.num = b.num, 1, 0)) AS equal,
  ABS(SUM(SIGN(a.num - b.num))) AS margin
FROM
  t a
  INNER JOIN t b
    ON 1 = 1
GROUP BY a.num)
SELECT
  AVG(num)
FROM
  t1
WHERE equal >= margin

由于我们对数据做了笛卡尔积的操作,因此实际上计算出来的 equal 和 margin 的值和演示时的值有差别。

本文分享自微信公众号 - SQL实现(gh_684ee9235a26),作者:zero

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 除了会排序,你对ORDER BY的用法可能一无所知!

    小伙伴们在进行SQL排序时,都能很自然的使用到ORDER BY。不管是默认ASC的升序,还是DESC降序,几乎都是信手拈来。

    白日梦想家
  • SQL 找出 100 以内的质数

    之前我写了一篇文章 SQL 生成斐波那契数列,在原来的基础上,今天就来实现使用 SQL 获取 100 以内的质数。

    白日梦想家
  • 不用 UNION 操作符实现 UNION 的效果

    当我们要合并两个表或者多个表的结果时,可使用 UNION ALL 或者 UNION 操作符, UNION 和 UNION ALL 的区别在于前者会对结果集去重...

    白日梦想家
  • mysql用户创建及授权

    一、 创建用户:  命令:CREATE USER 'username'@'host' IDENTIFIED BY 'password';  说明:usern...

    用户2038589
  • 功能式Python中的探索性数据分析

    这里有一些技巧来处理日志文件提取。假设我们正在查看一些Enterprise Splunk提取。我们可以用Splunk来探索数据。或者我们可以得到一个简单的提取并...

    大数据弄潮儿
  • try-catch的性能分析

    https://blog.csdn.net/lylwo317/article/details/51869893

    葆宁
  • JanusGraph数据备份与恢复

    JanusGraph官方文档并没有他提供数据备份与恢复的相关说明,所以我们是使用的Tinkerpop的备份与恢复命令。

    陈黎栋
  • Python学习之使用Python发送邮

    最近写的检查redis配置的脚本中需要增加一个发送邮件的功能,于是现学现用了python的邮件发送模块smtplib.可以参考《Python for Unix ...

    py3study
  • jenkins执行python脚本

    最新在研究使用jenkins做升级发布功能,大概的操作是选择产品、模块、环境等参数后,执行一个python脚本,脚本获取用户选择参数,然后执行发布动作。

    py3study
  • 《Drools7.0.0.Final规则引擎教程》第2章 追溯Drools5的使用

    2.1 Drools5简述 上面已经提到Drools是通过规则编译、规则收集和规则的执行来实现具体功能的。Drools5提供了以下主要实现API: Knowl...

    用户1161110

扫码关注云+社区

领取腾讯云代金券