0571：给定数字的频率查询中位数（★★）

力扣第 571 题

题目

Numbers 表：

+-------------+------+
| Column Name | Type |
+-------------+------+
| num         | int  |
| frequency   | int  |
+-------------+------+
num 是这张表的主键。这张表的每一行表示某个数字在该数据库中的出现频率。

中位数 是将数据样本中半数较高值和半数较低值分隔开的值。

编写一个 SQL 查询，解压 Numbers 表，报告数据库中所有数字的 中位数 。结果四舍五入至 一位小数 。

查询结果如下例所示。

输入：
Numbers 表：
+-----+-----------+
| num | frequency |
+-----+-----------+
| 0   | 7         |
| 1   | 1         |
| 2   | 3         |
| 3   | 1         |
+-----+-----------+
输出：
+--------+
| median |
+--------+
| 0.0    |
+--------+
解释：
如果解压这个 Numbers 表，可以得到 [0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3] ，所以中位数是 (0 + 0) / 2 = 0 。

分析

假设数组 A 的长度为 n，中位数是 x，那么要满足：

• A中 >=x 的个数 >=n//2
• A 中 <=x 的个数 >=n//2

解答

1
2
3
4
5
6
7

select avg(num) as median
from
    (select num, sum(frequency) over(order by num asc) as asc_amount, 
                    sum(frequency) over(order by num desc) as desc_amount,
                    sum(frequency) over() as total_num
    from numbers) a
where asc_amount >= total_num/2 and desc_amount >= total_num / 2 

135 ms