java - SortedList 允许重复和随机访问元素

Question

我正在开发一种算法，该算法在很大程度上依赖于某些列表中元素的顺序，但是，该列表需要允许重复和随机访问其元素(不使用迭代器)。我在java中搜索过这样的东西，但找到的选项总是缺少我提到的条件之一。

任何人都可以建议我用 java 解决这个问题，时间复杂度较低或适中吗？

如果我扩展 ArrayList 的类并重写方法 add，并在添加后的方法中调用 collection.sort()，这样在时间复杂度方面会好吗？

我认为添加一个元素需要一个常数时间，因为它是直接添加到列表的末尾，而sort方法需要n logn，那么在这种情况下，插入会花费n logn时间吗？

感谢任何帮助。

谢谢。

Answer 1

您可以使用 TreeMap，它按排序顺序和键出现的次数存储键，您可以存储为值。现在您可以遍历 Map 并填充 ArrayList(在键值大于 0 的地方填充重复项)总体复杂度为 nlogn空间复杂度log n

如果您扩展 ArrayList 并找到插入点/或调用 collections.sort()，您的算法在最佳情况下为 O(n^2 *logn)。如果您的 List 初始容量不足以进行所有插入，它将调整大小(额外的 O(n) 操作)