java - 在 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() 或 更多的 last() 调用>remove() 调用它来改变时间复杂度。

如果您确实执行了如此多的 last() 调用，这很重要，您可以自己缓存 last() 结果，并且只有在修改了自上次通话后设置。或者，一个 PriorityQueue可能更适合您的用例。

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