我想删除TreeSet中某个范围内的值，如下所示：
TreeSet<Integer> ts = new TreeSet<Integer>();
for(int i = 0; i < (int)1e7; i++){
ts.add((int)(Math.random() * 1e9));
}
System.out.println("ts: " + ts.size());
SortedSet<Integer> s = ts.subSet(500, (int)8e8);
s.clear();
System.out.println("ts: " + ts.size());此操作的运行时间是多少？
它是O(log(n))还是O(n)？我发现一些references声明subSet()操作需要log(n)。我还读到clear()操作是O(1)，但单个节点不会被清除，使其可能是O(n)吗？
1条答案
按热度按时间nx7onnlm1#
调用
TreSet#subSet返回原始集合的 view。创建此视图是O（1）。创建子集视图时不复制任何元素。视图上的大多数操作都委托给基础的原始集合。但是
clear()是个例外，在TreeSet上调用clear（实际上是TreeMap）是O（1），因为它只将大小设置为0并清除根节点。这对于
TreeSet的子集视图是不可能的，它需要逐个删除视图中的所有元素，委托给AbstractCollection#clear方法，该方法的实现如下：从
TreeMap的红黑树实现（其中TreeSet仅仅是一个 Package 器）中移除单个条目是O（log（n））。因此，移除N个条目（需要为子集视图完成）是O（n * log（n））。