劍指offer 資料流中的中位數

2022-11-24 15:01:36 字數 395 閱讀 6505

如何得到一個資料流中的中位數?如果從資料流中讀出奇數個數值,那麼中位數就是所有數值排序之後位於中間的數值。如果從資料流中讀出偶數個數值,那麼中位數就是所有數值排序之後中間兩個數的平均值。我們使用insert()方法讀取資料流,使用getmedian()方法獲取當前讀取資料的中位數。

思路:利用兩個優先佇列,最大堆始終儲存前一半資料,最小堆始終儲存後一半資料,當兩個優先佇列長度一樣時,將數壓入最小堆。

1

class

solution else

17 } else else26}

27}2829

double

getmedian()

30 else

3637}38

39 };

劍指offer 資料流中的中位數

如何得到一個資料流中的中位數?如果從資料流中讀出奇數個數值,那麼中位數就是所有數值排序之後位於中間的數值。如果從資料流中讀出偶數個數值,那麼中位數就是所有數值排序之後中間兩個數的平均值。我們使用insert 方法讀取資料流,使用getmedian 方法獲取當前讀取資料的中位數。使用堆排序思想 建立一...

劍指offer 41 資料流中的中位數

這道題涉及到對堆這個資料結構的使用,落實到 上實際使用的是優先佇列 優先佇列底層可以通過堆來實現 題目描述 如何得到一個資料流中的中位數?如果從資料流中讀出奇數個數值,那麼中位數就是所有數值排序之後位於中間的數值。如果從資料流中讀出偶數個數值,那麼中位數就是所有數 值排序之後中間兩個數的平均值。例如...

劍指offer63 資料流中的中位數

如何得到一個資料流中的中位數?如果從資料流中讀出奇數個數值,那麼中位數就是所有數值排序之後位於中間的數值。如果從資料流中讀出偶數個數值,那麼中位數就是所有數值排序之後中間兩個數的平均值。我們使用insert 方法讀取資料流,使用getmedian 方法獲取當前讀取資料的中位數。進位制轉化 排序 堆 ...