# 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');
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zqt0.gitbook.io/leetcode/sql/571.find-median-given-frequency-of-numbers.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.