首頁猿問從整數(shù)流中查找運(yùn)行中位數(shù)

從整數(shù)流中查找運(yùn)行中位數(shù)

算法與數(shù)據(jù)結(jié)構(gòu)

蝴蝶不菲 2019-11-04 14:47:20

假定從數(shù)據(jù)流中讀取整數(shù)。查找迄今為止有效讀取的元素的中位數(shù)。我已閱讀的解決方案：我們可以在左側(cè)使用最大堆表示小于有效中位數(shù)的元素，在右側(cè)使用最小堆表示大于有效中位數(shù)的元素。處理傳入的元素后，堆中的元素?cái)?shù)量最多相差1個(gè)元素。當(dāng)兩個(gè)堆包含相同數(shù)量的元素時(shí)，我們發(fā)現(xiàn)堆根數(shù)據(jù)的平均值為有效中位數(shù)。當(dāng)堆不平衡時(shí)，我們從包含更多元素的堆根中選擇有效中位數(shù)。但是，我們將如何構(gòu)造最大堆和最小堆，即我們?nèi)绾沃烙行е形粩?shù)？我認(rèn)為我們將在max-heap中插入1個(gè)元素，然后在min-heap中插入下一個(gè)1個(gè)元素，以此類推。糾正我，如果我在這里錯(cuò)了。

查看完整描述

3 回答

拉風(fēng)的咖菲貓

TA貢獻(xiàn)1995條經(jīng)驗(yàn) 獲得超2個(gè)贊

從流數(shù)據(jù)中查找運(yùn)行中位數(shù)有很多不同的解決方案，我將在答案的最后簡(jiǎn)短地討論它們。

問題是有關(guān)特定解決方案（最大堆/最小堆解決方案）的詳細(xì)信息，下面說明基于堆的解決方案如何工作：

對(duì)于前兩個(gè)元素，在左側(cè)的maxHeap中添加較小的元素，在右側(cè)的minHeap中添加較大的元素。然后一一處理流數(shù)據(jù)，

Step 1: Add next item to one of the heaps

if next item is smaller than maxHeap root add it to maxHeap,

else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or

one of them will contain 1 more item)

if number of elements in one of the heaps is greater than the other by

more than 1, remove the root element from the one containing more elements and

add to the other one

然后，您可以在任何給定時(shí)間像這樣計(jì)算中位數(shù)：

If the heaps contain equal amount of elements;

median = (root of maxHeap + root of minHeap)/2

Else

median = root of the heap with more elements

現(xiàn)在，我將按照答案開頭所承諾的一般性地討論這個(gè)問題。從數(shù)據(jù)流中找到運(yùn)行中位數(shù)是一個(gè)棘手的問題，并找到一個(gè)確切的解決方案與內(nèi)存的限制有效地大概是不可能的一般情況。另一方面，如果數(shù)據(jù)具有我們可以利用的某些特征，那么我們可以開發(fā)有效的專用解決方案。例如，如果我們知道數(shù)據(jù)是整數(shù)類型，則可以使用計(jì)數(shù)排序，可以為您提供恒定的內(nèi)存恒定時(shí)間算法?；诙训慕鉀Q方案是一種更通用的解決方案，因?yàn)樗部梢杂糜谄渌麛?shù)據(jù)類型（雙精度）。最后，如果不需要精確的中位數(shù)并且近似值足夠，則可以嘗試估計(jì)數(shù)據(jù)的概率密度函數(shù)，并使用該函數(shù)估計(jì)中位數(shù)。

反對(duì) 回復(fù) 2019-11-04