在 TreeSet O(1) 时间内获取最大元素？

Question

调用 last() 会得到最大的元素，但它是 O(logN) 时间，我知道在 C++ 中我可以利用迭代器并且调用 rbegin() 是常数时间，我可以吗在获取最大元素时用 Java 的 TreeSet 实现这个常数时间？

C++ 示例代码：

set<int> s;

s.insert(5);
s.insert(3);
s.insert(7);
... // say I inserted a total of n elements.
s.insert(0);
s.insert(9999);

cout<<*s.begin()<<endl;  //0
cout<<*s.rbegin()<<endl; //9999

Answer 1

TreeSet 不跟踪提供对最大元素的恒定时间访问所需的额外数据。这不太可能影响任何使用 TreeSet 的算法的时间复杂度，因为您必须执行比 add() 或 remove() 调用更多的 last() 调用才能更改时间复杂性。

如果您确实执行了如此多的 last() 调用，这很重要，您可以自己缓存 last() 结果，并且只有在自上次调用后修改了集合时才重新计算它。或者，PriorityQueue 可能更适合您的用例。

（std::set 确实跟踪此数据的事实意味着它必须对重组集合的操作执行额外的工作，即使您不需要它。）

在 TreeSet O(1) 时间内获取最大元素？

Getting biggest element in TreeSet O(1) time?

c++

java

iterator

hashset

binary-search-tree