> For the complete documentation index, see [llms.txt](https://zqt0.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zqt0.gitbook.io/leetcode/sql/571.find-median-given-frequency-of-numbers.md).

# 571.(Hard)给定数字的频率查询中位数

Numbers 表保存数字的值及其频率。

```
+----------+-------------+
|  Number  |  Frequency  |
+----------+-------------|
|  0       |  7          |
|  1       |  1          |
|  2       |  3          |
|  3       |  1          |
+----------+-------------+
```

在此表中，数字为 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3，所以中位数是 (0 + 0) / 2 = 0。

```
+--------+
| median |
+--------|
| 0.0000 |
+--------+
```

请编写一个查询来查找所有数字的中位数并将结果命名为 median 。

来源：力扣（LeetCode）

链接：<https://leetcode-cn.com/problems/find-median-given-frequency-of-numbers>

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## Solution

总体思路是 1. **计算每个number正序、倒序的排序**，两个方法（窗口函数更高效）

* 窗口函数法 `sum(frequency) over(order by number)`
* 子查询法 `select sum(frequency) from Numbers where t.number>=number)`&#x20;

1. 选出位于正中间的数字，两种判别方式
   * 正序asc和倒序desc都大于等于总数的一半：  `asc >= total/2 and desc >= total/2`
   * 偏差bias=abs(asc-desc) 大于等于 自身freq：  `bias >= freq`

```
Number  Frequency   total   asc     desc   bias
0            7      12      7        12    5
1            1      12      8        5     3
2            3      12      11       4     8
3            1      12      12       1     11
```

```sql
-- subquery
select avg(number) median
from Numbers t
where t.frequency >= abs(
    (select sum(frequency) from Numbers where t.number>=number) -
    (select sum(frequency) from Numbers where t.number<=number)
)

-- window 1
select avg(number) as median
from
(select *, 
abs(sum(frequency) over(order by number asc)-sum(frequency) over(order by number desc)) bias
from numbers) a
where frequency >= bias

-- window 2
select avg(number) as median
from
(select number, sum(frequency) over(order by number asc) as asc_amount, 
                sum(frequency) over(order by number 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
```

## Table Schema

```sql
Create table If Not Exists Numbers (Number int, Frequency int);
Truncate table Numbers;
insert into Numbers (Number, Frequency) values ('0', '7');
insert into Numbers (Number, Frequency) values ('1', '1');
insert into Numbers (Number, Frequency) values ('2', '3');
insert into Numbers (Number, Frequency) values ('3', '1');
```