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)
选出位于正中间的数字,两种判别方式
正序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
-- 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
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');
Last updated
Was this helpful?