排序列表，允許重複和元素的隨機存取

我正在開發主要依賴內部的一些列表元素的次序上的算法，然而，該列表需要允許重複和隨機訪問其元素（不使用iterator）。我用java搜索了這樣的東西，但是找到的選項總是缺乏我提到的條件之一。排序列表，允許重複和元素的隨機存取

任何人都可以請建議我要這個問題在Java的解決方案，具有低或中等的時間複雜度？

如果我擴展的類的ArrayList和覆蓋的方法添加，而添加後我打電話collection.sort（）會，關於時間複雜度是不錯的方法裏面？

我想添加元素需要一定的時間，因爲它直接添加到列表的末尾，和排序方法佔據N LOGN，所以在這種情況下，將在插入取n LOGN時間？

任何幫助表示讚賞。

謝謝。

2015-04-02 Dania

可能重複的[Java List Sorting：有沒有一種方法可以像TreeMap一樣自動對列表進行排序？（http://stackoverflow.com/questions/4903611/java-list-sorting-is-there-a-way-to-keep-a-list-permantly-sorted-automatically） – azurefrog 2015-04-02 18:35:09

您可能還需要採取看看[這個問題]（http://stackoverflow.com/questions/8725387/why-is-there-no-sortedlist-in-java）。這是一個更普遍的目的，但也可能對你有用。 – azurefrog 2015-04-02 18:36:08

謝謝你提供這個鏈接，但我需要一個算法來實現，如果你能提供給我任何提示或建議，這將是一個很大的幫助。謝謝 – Dania 2015-04-02 18:38:48

您可以使用存儲在有序的按鍵和倍鍵數出現一個TreeMap，你可以存儲爲的值。現在你可以遍歷地圖和（其中一個鍵的值大於0時填寫一式兩份）總體複雜性填充的ArrayList是nlogn 空間複雜度爲log N

如果擴展ArrayList和找到插入點/或調用集合.sort（）在最好的情況下，你的算法是O（n^2 * logn）。如果您的List初始容量不足以支持所有插入，它將調整大小（額外的O（n）操作）

來源

2015-04-02 19:38:52 bl3e

很好的答案，謝謝。是否有可能根據值而不是鍵對樹進行排序？ – Dania 2015-04-03 16:23:30

是的，你可以實現一個比較器/或比較關鍵類比較使用值...這將需要在地圖上的額外查找。 – bl3e 2015-04-04 20:35:33

非常感謝@ bl3e – Dania 2015-04-05 06:39:27

你可以嘗試從谷歌的番石榴庫TreeMultiset。它沒有索引隨機訪問器，但可以通過指定範圍邊界來訪問子列表。

http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/index.html

來源

2015-04-02 19:19:41 whaleberg

我會通過番石榴檢查這個選項，謝謝你的有用答案 – Dania 2015-04-03 16:23:57

排序列表，允許重複和元素的隨機存取

回答

相關問題