數據結構

Question

有大量數據流進入，例如5 6 7 2 3 1 2 3 ..考慮到元素必須按降序插入並且重複應該插入的約束，什麼樣的數據結構適合這個問題被淘汰。

我不是在尋找任何代碼只是想法？我正在考慮自我平衡BST，我們可以添加條件，所有節點在當前節點左邊，所有節點>當前節點在右邊，這將照顧重複..但我不認爲他們必須插入按降序排列。任何想法什麼可能是一個更好的選擇..課程需要有效的時間和空間的明智。

Answer 1

平衡二叉樹很好。您將在O（log N）時間查找或插入每個副本，其中N是樹中已有元素的數量，因此總體上爲O（N log N）。並且插入是有序的 - 您可以通過反轉比較來決定順序。

然後，您只需在深度一階完成後讀出它，並且瞧不出重複的降序值。

你流5 6 7 2 3 1 2 3將導致：

 A> 5   B> 5   C> 6 
        /   /\ 
         6    7 5 

    D> 6   E> 6   F> 5 
    /\   /\   /\ 
     7 5   7 3   6 2 
      \   /\  //\ 
      2   5 2  7 3 1 

那麼最後2和3被丟棄，因爲它們在樹中已經存在。而且，當您遞歸處理樹（左，當前，右）時，您可以根據需要獲得7, 6, 5, 3, 2, 1。

---

另一種解決辦法，如果你有一個數字的有限範圍內，是一個布爾地圖。假設輸入範圍僅爲數字0到9.

設置一個10元素的布爾數組並將所有值設置爲false。他們爲每個數字設置相應的值爲true。

因此，對於您輸入（空白是假的，t爲true）：

 <booleans> 
    
i 5|  t 
n 6|  tt 
p 7|  ttt 
u 2| t ttt 
t 3| tt ttt 
| 1| ttt ttt 
| 2| ttt ttt 
V 3| ttt ttt 

布爾地圖將輸出7, 6, 5, 3, 2, 1的向後處理。

一旦收到所有數字，按照相反的順序通過數組並輸出數值爲真的數字。這是一個可能需要更多空間的時間操作（這是一個通用規則，您可以在開發算法時經常爲空間換取空間）。

這也適用於範圍不是從0開始 - 你只需要在範圍的低端偏移一切。所以如果範圍是100到109，你仍然會有一個10元素的數組，其索引i代表數字i + 100。

但是，如果範圍很大，數字稀疏，我會堅持使用樹結構。

Answer 2

這在一定程度上取決於重複樣本與總樣本大小的比率。

高重複定額可能更容易解決，無論是隻是一個散列（其中的鍵每隔一段時間排序到一個有序列表中），或者與一個散列和一個空白樹的組合（散列用於過濾出重複項）。

重複率低，只要按照您的建議去平衡樹。

Answer 3

既然你已經得到了簡單的數據只是數字你爲什麼不使用存儲陣列中的一個二元堆？當然，你應該知道元素數量的上限，以避免重新分配它。