假定從數據流中讀取整數。查找迄今為止有效讀取的元素的中位數。我已閱讀的解決方案：我們可以在左側使用最大堆表示小于有效中位數的元素，在右側使用最小堆表示大于有效中位數的元素。處理傳入的元素后，堆中的元素數量最多相差1個元素。當兩個堆包含相同數量的元素時，我們發現堆根數據的平均值為有效中位數。當堆不平衡時，我們從包含更多元素的堆根中選擇有效中位數。但是，我們將如何構造最大堆和最小堆，即我們如何知道有效中位數？我認為我們將在max-heap中插入1個元素，然后在min-heap中插入下一個1個元素，以此類推。糾正我，如果我在這里錯了。
3 回答
拉風的咖菲貓
TA貢獻1995條經驗 獲得超2個贊
從流數據中查找運行中位數有很多不同的解決方案，我將在答案的最后簡短地討論它們。
問題是有關特定解決方案（最大堆/最小堆解決方案）的詳細信息，下面說明基于堆的解決方案如何工作：
對于前兩個元素，在左側的maxHeap中添加較小的元素，在右側的minHeap中添加較大的元素。然后一一處理流數據，
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
然后，您可以在任何給定時間像這樣計算中位數：
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
現在，我將按照答案開頭所承諾的一般性地討論這個問題。從數據流中找到運行中位數是一個棘手的問題，并找到一個確切的解決方案與內存的限制有效地大概是不可能的一般情況。另一方面，如果數據具有我們可以利用的某些特征，那么我們可以開發有效的專用解決方案。例如，如果我們知道數據是整數類型，則可以使用計數排序，可以為您提供恒定的內存恒定時間算法?；诙训慕鉀Q方案是一種更通用的解決方案，因為它也可以用于其他數據類型（雙精度）。最后，如果不需要精確的中位數并且近似值足夠，則可以嘗試估計數據的概率密度函數，并使用該函數估計中位數。
添加回答
舉報
0/150
提交
取消