我需要一个 Java 数据结构:
- 快速(O(1))插入
- 快速删除
- 快速 (O(1))
max()函数
最好的数据结构是什么？
HashMap 几乎可以工作，但使用 java.util.Collections.max() 至少是 map 大小的 O(n)。 TreeMap 的插入和移除太慢了。
有什么想法吗？
最佳答案
O(1) 插入和O(1) max() 与快速移除点是互斥的。
O(1) 插入集合不会有 O(1) max 因为集合是未排序的。必须对 O(1) max 集合进行排序，因此插入是 O(n)。你必须硬着头皮在两者之间做出选择。然而，在这两种情况下，移除速度应该同样快。
如果你可以忍受缓慢的移除，你可以有一个变量保存当前最高的元素，比较插入与那个变量，max 和 insert 应该是 O(1) 那么。不过，移除的时间复杂度为 O(n)，因为在移除的元素最高的情况下，您必须找到新的最高元素。
关于java - 哪个是合适的数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5773096/