在O（log n）中找到中位數

問題是我們如何找到整數值的接收流的中值（例如，對於12,14,252,243,15的中位數爲15），在O（logN ）其中N是值的數目。請注意，我們有一串整數值，因此通過接收每個值，我們必須重新找到中值。在O（log n）中找到中位數

實施例：

| Input | median 
1 | 12 | 12 
2 | 14 | 13 = (12+14)/2 
3 | 252 | 14 
. 
. 
.

P.S：使用該算法可以是濾波的圖像的一個例子。

來源

2011-10-20 csuo

除非數據被排序並可隨機訪問，否則我相當確定您希望的最好線性複雜性。 –

嗨，傑裏，你是對的，當我們有一個N值的列表，所以在這種情況下，我們應該對列表進行排序（O（N log N）），但正如我所提到的，這裏的問題有點不同，我們有輸入 – csuo

感謝您的評論，我做了 – csuo

好的，隨着問題的更新，意圖很清楚（不僅找到中位數，而且每次收到新號碼時都要重新找到中位數），我認爲這是一種方法。

我會從一堆堆開始：一個最大堆和一個最小堆。最小堆將包含大於中位數的數字，最大堆數小於中位數。當你收到第一個號碼時，這是你的中位數。當你收到第二個時，你將兩個中的較小者插入到最大堆中，並將兩個中的較大者插入最小堆中。那麼中位數就是最小堆中最小的平均值，最大堆中的最大值。

除了兩堆之外，您還需要存儲單個整數，當您收到奇數個輸入時，該整數將成爲當前的中位數。你將很簡單地填充它：如果你接收到一個輸入，它現在已經滿了，你基本上對這兩個項目（新數字和舊中值）進行排序，並將較小的項目插入堆中，將更大的項插入堆中爲更大的項目。您的新的中位數將是這兩個堆的基數的平均值（並且您將其他存儲位置標記爲空）。

當您收到一個空的新號碼時，您會將新號碼與中位數進行比較。如果它位於數字之間作爲堆的基數，則它是新的中位數，然後就完成了。否則，從必須保持中位數的基數中提取數字（如果新數字較大，則數字較大，如果較小，則數字較小），並將其放入中位數點，然後將新數字插入到來自的堆中。

至少如果內存服務，提取/插入到堆中應該是O（log N）。我相信所有其他涉及的應該是不斷複雜的。

來源

2011-10-20 22:35:05

不錯的解決方案。（我相信extract-min也是O（log N），它不會改變整體的強度） – Nemo

明智的解決方案！ +1 – kyun

如果流的緩衝區是有限的，則此解決方案將不起作用，並且您需要在元素滿足其進入順序後才移除元素。堆取O（N）進行搜索。然而，你可以使用某種二叉搜索樹而不是堆，並且所有的操作都是O（log（N）） – umps

（我假設你認爲，鑑於ñ現有的數字和一個新號碼的算法後的時候，需要對數時間找到N + 1號碼的新集合的中位數，從而使總運行時間增加ň數字將爲O（n LG N））

有可能是一個名爲算法這個了，但這裏是我的想法：保持你插入其中一個紅黑樹數字，他們到達。在每個節點中，除了數字本身和子/父指針之外，還存儲一個整數，用於指示該節點下方存在的節點數（包括節點本身，爲了方便起見）。我很確定，即使在需要樹輪旋轉時，這些信息也可以在每次插入操作的對數時間內更新。通過將這些信息嵌入樹中，如果您也跟蹤樹中的節點數，那麼定位中值可以在對數時間內完成。

（這可能是一個稍微有點高層次的描述，讓我知道，如果你需要更多的細節。）

來源

2011-10-20 21:23:52

O（n lg n）？簡單地排序和選擇中間元素.. –

你是絕對正確的，我試圖完全按照你所說的做，但問題是，通過標記每個節點的子節點數量來找到中位數有點困難 – csuo

這是描述詳細分析如下：算法簡介（第二版） - 14.3：增加數據結構 - 間隔樹 –

Hoare's selection algorithm（又名quickselect）可以在O做到這一點（n）的平均時間。

它基本上是遞歸地用隨機數據集分區數據集並檢查相應的部分。還有一個median of medians algorithm它保證了O（n）最差的時間複雜度，但對於正常的使用它通常是一個矯枉過正。

來源

2011-10-20 21:47:20

我認爲他正在尋找一種在線算法，對於輸入的每個新號碼，都可以產生新的數字集合的中位數。這可以比中值選擇更快地完成。 –

他在問題中沒有提到這個問題，如果是這種情況，那麼區間樹是完美的......並且如果他只需要整個流的中位數然後快速選擇。 –

在O（log n）中找到中位數

回答

相關問題