我正在开发一种算法，该算法在很大程度上依赖于某些列表中元素的顺序，但是，该列表需要允许重复和随机访问其元素(不使用迭代器)。我在java中搜索过这样的东西，但找到的选项总是缺少我提到的条件之一。
任何人都可以建议我用 java 解决这个问题，时间复杂度较低或适中吗？
如果我扩展 ArrayList 的类并重写方法 add，并在添加后的方法中调用 collection.sort()，这样在时间复杂度方面会好吗？
我认为添加一个元素需要一个常数时间，因为它是直接添加到列表的末尾，而sort方法需要n logn，那么在这种情况下，插入会花费n logn时间吗？
感谢任何帮助。
谢谢。
最佳答案
您可以使用 TreeMap，它按排序顺序和键出现的次数存储键，您可以存储为值。 现在您可以遍历 Map 并填充 ArrayList(在键值大于 0 的地方填充重复项) 总体复杂度为 nlogn 空间复杂度log n
如果您扩展 ArrayList 并找到插入点/或调用 collections.sort()，您的算法在最佳情况下为 O(n^2 *logn)。 如果您的 List 初始容量不足以进行所有插入，它将调整大小(额外的 O(n) 操作)
关于java - SortedList 允许重复和随机访问元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29420004/