[leetcode][Database][Hard] 571. Find Median Given Frequency of Numbers
4 min readDec 6, 2022
題目
Table: Numbers
+-------------+------+
| Column Name | Type |
+-------------+------+
| num | int |
| frequency | int |
+-------------+------+
num is the primary key for this table.
Each row of this table shows the frequency of a number in the database.
The median is the value separating the higher half from the lower half of a data sample.
Write an SQL query to report the median of all the numbers in the database after decompressing the Numbers
table. Round the median to one decimal point.
SQL Schema
Create table If Not Exists Numbers (num int, frequency int)
Truncate table Numbers
insert into Numbers (num, frequency) values ('0', '7')
insert into Numbers (num, frequency) values ('1', '1')
insert into Numbers (num, frequency) values ('2', '3')
insert into Numbers (num, frequency) values ('3', '1')
解題思考
- 題目要求輸出
Numbers
表格的中位數median
。
本題要求的邏輯為 :
1. 先將Numbers
內的數字num
以頻次frequency
展開為等長的數列
2. L ← 將所有num
展開的數列依num
大小有序串接
3. 求出 L 的中位數median
,並將中位數作為輸出結果
Input:
Numbers table:
+-----+-----------+
| num | frequency |
+-----+-----------+
| 0 | 7 |
| 1 | 1 |
| 2 | 3 |
| 3 | 1 |
+-----+-----------+
Output:
+--------+
| median |
+--------+
| 0.0 |
+--------+
Explanation:
If we decompress the Numbers table,
we will get [0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3],
so the median is (0 + 0) / 2 = 0.
- 中位數的定義 → 在一組數列 S 中,有一半數字個數會小於中位數,另外一半數字個數會大於中位數。假設
L ← 數列 S 中,小於等於Numbers.num
的數字個數
R ← 數列 S 中,大於等於Numbers.num
的數字個數
N ← 數列 S 中,Numbers.num
的數字個數
則數列 S 的數字個數應等同於L + N + R
, 對Numbers
中的所有num
,該條件都成立 - 考慮當 L ≠ R 的情況,若
Numbers.num
是中位數,當 N 加入至個數較少的短邊
時 ( L 或 R ) ,被 N 加入的短邊
會成為長邊
:
當 L < R,L + N > R
當 R < L,R + N > L
若Numbers.num
不是中位數,當 L < R 時,即使把 N 放到短邊,仍會得到 L + N < R 的結果,這表示 N 不在數列中間 - 考慮當 L = R 的情況,根據定義已知
Numbers.num
是中位數
解決方案
select
round(avg(n.num),1) median
from Numbers n
where
n.Frequency >= abs(
(select sum(Frequency) from Numbers where num<=n.num) -
(select sum(Frequency) from Numbers where num>=n.num)
)