特定問題的數據結構？

在最壞的情況下，哪個數據結構可以在O（1）時間內執行插入，刪除和搜索操作？特定問題的數據結構？

我們可以假設元素集合是從有限集合1,2，...，n中繪製的整數，初始化可以花費O（n）個時間。

我只能想到實現一個哈希表。

用樹實現它不會給任何操作帶來O（1）的時間複雜性。或者有可能？

請分享您的看法，或任何其他數據結構，除了這些..

謝謝..

2010-05-23 AGeek

你真的只想存儲已知上限的整數嗎？如果是這樣，ROMANARMY將它釘牢。如果你真的想存儲別的東西，你應該讓我們知道。 – luke 2010-05-23 05:14:56

雖然這聽起來像功課，給予了足夠的內存，你可以只使用一個陣列。訪問任何一個元素將是O（1）。如果您使用每個單元格來保持遇到該類型的整數的數量，插入也將是O（1）。搜索將是O（1），因爲它需要索引該索引處的數組並查看計數。這基本上是基數排序的工作原理。

2010-05-23 05:05:26 R0MANARMY

我喜歡它！這必須是我讀過的世界上最簡單的散列表實現。當然你犧牲一點普遍性，但看看實現的簡單性的收益！ +1 – luke 2010-05-23 05:12:57

那麼它不是一個家庭作業,,但是yaa我正在努力解決算法的一些問題，我自己也就是個人興趣，並嘗試通過這個論壇尋求儘可能多的經驗..這個論壇很有用！和非常有經驗的人在那裏解決一個人的疑問..非常感謝.. +1 .. – AGeek 2010-05-23 05:18:50

@ AGeek：在這種情況下，你可能也喜歡這個鏈接http://kevinrodrigues.com/blog/2010/02/06/你可以排序10萬個數字使用1mb的內存/ – R0MANARMY 2010-05-23 05:38:53

取決於數組可能做的元素範圍，但對於需要散列表的大量數據。它會給你O（1）攤銷操作。

2010-05-23 08:39:42

回答