將數組轉換爲中值數組

我在思考以下問題的解決方案：我有一個整數的大數組（甚至更困難的情況下是一個整數流），我想將該數組轉換爲中數組，它的位置對應於數組[0..i]的中位數。將數組轉換爲中值數組

現在，我的蠻力方法將針對每個子數組，然後對其進行排序，然後選擇中間元素。那就是O（n^2 log n），因爲每n個子數組必須按照N log N次排序。我可以使用一些計數機制將時間降低到N^2，但N^2是否可以做到最好？

2013-01-11 Bober02

的答案（具體包括在其中的參考文獻）這個（關閉）的問題可以幫助你http://stackoverflow.com/questions/3440905/find整數的中間值 –

使用選擇算法而不是排序可以平凡地提高「O（n^2）」的複雜度，儘管我的直覺告訴我有更高效的方法，可能'O（nlogn）'一個。 – amit

將單個項目插入已排序的樹形結構中，例如，一棵紅黑色的樹，將採取O（日誌n）。如果維護每個節點的後代數量，則可以在O中完成查找中位數（日誌n）。這樣做可以爲您的流中的所有元素提供n元素，並且您有一個O（n日誌n）算法。

的數據結構和值計算可能是這個樣子：

struct TreeNode { 
    enum { RED, BLACK } color; 
    size_t numElements; 
    int value; 
    TreeNode* left, right; 
} *root; 

TreeNode* treeSelect(TreeNode *top, size_t count) { 
    if (top->left != NULL) { 
    if (count < top->left->numElements) 
     return treeSelect(top->left, count) 
    count -= top->left->numElements; 
    } 
    if (count == 0) 
    return top; 
    return treeSelect(top->right, count - 1); 
} 

TreeNode* treeMedian() { 
    return treeSelect(root, root->numElements/2); 
}

其他操作是那些通常用於紅黑樹，儘管你可以跳過那些刪除節點。您可以調整它們以使用重複元素。這裏的一般規則是，當要插入的元素等於當前節點的元素時，可以插入任何子樹。並且在平衡樹時，應該保留重複鍵的順序，以便維護附屬子樹的順序。但是，除非我錯過了一些東西，否則平衡在任何情況下都不會進行價值比較，所以一旦插入了重複項，就完成了。如果你期望真的有很多重複的值，你可以使用類似multimap的方法，在每個節點中都有一個計數器。

來源

2013-01-11 11:56:43 MvG

所以這棵樹必須始終保持平衡才能完成這項工作？另外，如果有重複的元素呢？ – Bober02

以及如何找到給定樹的中位數？ – Bober02

@ Bober02，樹必須在紅黑樹的限制內平衡，以保證最壞情況時間複雜度的限制。我更新了我的答案，以討論重複的元素，並草擬了中位數查找過程。 – MvG

它可以O(nlogn)完成下列方法處理：

使用跳躍列表（或B +樹），以保持數據流。
還保持一個指向當前中位數的指針。

在每次迭代中，讓節點的數量是n，中位數（值）爲m，您將看到新的值是x（插入剛到元素之前）。

插入x到跳躍列表
如果n%2 ==0（中位數的指標應該增加）：
如果x < m.value：沒有變化需要的m指數也增加
其他：設置m <- m.next
其他：（中位數的指數應保持不變）
如果x < m.value：設置m <- m.previous //因爲m的指數提高
其他：無需更改。// m的指數沒有增加
m.value爲下一個元素

找到前一個/下中值是O(1)，插入x是O(logn) - 總複雜性是O(nlogn)與O(n)額外的空間。

注：應特別注意補充如果流可以包含重複的元素，和skiplist應該有這方面的確定性的行爲 - 即插入總是最後一個可能的索引

來源

2013-01-11 12:00:41 amit

strea/array肯定會有重複項 – Bober02

使用一些快速BST像AVL或展曲。您可以簡單地修改結構，以便每個節點在時間內可以獲得其子樹的中位數。特別是你可以得到樹中所有項目的中位數。

現在你正在做的事情是這樣的：

Create empty BST 
foreach n in stream: 
    Insert n to BST 
    Get median from BST.root

來源

2013-01-11 12:31:40 Ari

您通常不希望來自子樹的* median *，而是指定索引處的元素，它將是整個樹的中值。 – MvG

是的，你是對的 – Ari

正確，所以主要的要求是樹必須始終保持平衡？ – Bober02

將數組轉換爲中值數組

回答

相關問題