設計一個帶插入，刪除的數據結構，在O（1）時間複雜度中獲得隨機數，

這是一個最近的面試問題。請設計一個帶有插入，刪除的數據結構，在o（1）時間複雜度中獲得隨機數，數據結構可以是數組等基本數據結構，可以是基本數據結構的修改，也可以是基本數據的組合結構。設計一個帶插入，刪除的數據結構，在O（1）時間複雜度中獲得隨機數，

來源

2014-02-28 feliciafay

關於什麼可能是解決方案的一些想法？ :)你在哪裏遇到問題？ –

@jkbkot在採訪中我沒有給出正確答案。我試圖組合一個哈希表和一個鏈表。根據面試官的意見，這不是一個足夠好的答案。然而，考慮組合不同的數據結構是正確的方向。 – feliciafay

（好）面試官通常對你對問題的看法比對確切的解決方案更感興趣。例如，對於這個特定的問題，你可以詢問元素的最大數量是多少。如果有一些，那麼答案將是一個數組。如果沒有，你會開始考慮更復雜的解決方案。如果沒有限制，它可能沒有O（1）中的解決方案，那麼您可能會獲得良好的平均或攤銷複雜性，例如通過加倍數組的大小，等等。 –

將數組與元素的散列圖組合到數組索引中。

插入可以通過追加到數組並添加到散列圖來完成。

刪除可以通過首先查找並移除哈希映射中的數組索引，然後將最後一個元素與數組中的該元素進行交換，相應地更新先前的最後一個元素的索引並將數組大小減少一（刪除最後一個元素）。

通過返回數組中的隨機索引可以完成隨機操作。

所有的操作都是O（1）。

那麼，在現實中，它是分期（從調整數組的大小）預期（從預期的哈希碰撞）O（1），但足夠接近。

來源

2014-02-28 00:40:01 Dukeling

碰撞怎麼辦？我不確定你可以忽略增加和減少數組大小的複雜性。 –

這是最優雅的解決方案！我希望我已經這樣回答了。非常感謝你:) – feliciafay

@jkbkot當然，它不是真正的O（1）（它是預期的O（1）），但這很可能是他們尋找的答案。 – Dukeling

基數樹可以工作。見http://en.wikipedia.org/wiki/Radix_tree。插入和刪除是O（k），其中k是密鑰的最大長度。如果所有密鑰長度相同（例如，所有指針），則k是常數，所以運行時間是O（1）。

爲了實現獲得隨機性，維護每個子樹（O（k））中樹葉總數的記錄。樹中的葉子總數記錄在根部。要隨機選擇一個，生成一個隨機整數來表示要選擇的元素的索引。遞歸掃描樹，始終跟隨包含所選元素的分支。你總是知道選擇哪個分支，因爲你知道每個子樹可以達到多少葉子。樹的高度不超過k，所以當k是常數時，這是O（k）或O（1）。

來源

2014-02-28 00:37:25 Callum

這可能更適合於實時系統，然後接受答案（依賴於分期付款）可能會產生問題。 – Callum

設計一個帶插入，刪除的數據結構，在O（1）時間複雜度中獲得隨機數，

回答

相關問題