我在思考以下問題的解決方案:我有一個整數的大數組(甚至更困難的情況下是一個整數流),我想將該數組轉換爲中數組,它的位置對應於數組[0..i]的中位數。將數組轉換爲中值數組
現在,我的蠻力方法將針對每個子數組,然後對其進行排序,然後選擇中間元素。那就是O(n^2 log n),因爲每n個子數組必須按照N log N次排序。我可以使用一些計數機制將時間降低到N^2,但N^2是否可以做到最好?
我在思考以下問題的解決方案:我有一個整數的大數組(甚至更困難的情況下是一個整數流),我想將該數組轉換爲中數組,它的位置對應於數組[0..i]的中位數。將數組轉換爲中值數組
現在,我的蠻力方法將針對每個子數組,然後對其進行排序,然後選擇中間元素。那就是O(n^2 log n),因爲每n個子數組必須按照N log N次排序。我可以使用一些計數機制將時間降低到N^2,但N^2是否可以做到最好?
將單個項目插入已排序的樹形結構中,例如,一棵紅黑色的樹,將採取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的方法,在每個節點中都有一個計數器。
它可以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.value
爲下一個元素找到前一個/下中值是O(1)
,插入x
是O(logn)
- 總複雜性是O(nlogn)
與O(n)
額外的空間。
注:應特別注意補充如果流可以包含重複的元素,和skiplist應該有這方面的確定性的行爲 - 即插入總是最後一個可能的索引
strea/array肯定會有重複項 – Bober02
的答案(具體包括在其中的參考文獻)這個(關閉)的問題可以幫助你http://stackoverflow.com/questions/3440905/find整數的中間值 –
使用選擇算法而不是排序可以平凡地提高「O(n^2)」的複雜度,儘管我的直覺告訴我有更高效的方法,可能'O(nlogn)'一個。 – amit