据我所知它是 O(n^2) 还是它?
/**
* Retains only the elements in this list that are contained in the
* specified collection. In other words, removes from this list all
* of its elements that are not contained in the specified collection.
*
* @param c collection containing elements to be retained in this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean retainAll(Collection<?> c) {
return batchRemove(c, true, 0, size);
}
boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// Optimize for initial run of survivors
for (r = from;; r++) {
if (r == end)
return false;
if (c.contains(es[r]) != complement)
break;
}
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally {
modCount += end - w;
shiftTailOverGap(es, w, end);
}
return true;
}
最佳答案
假设我们的 ArrayList<T>
有n
元素,和 Collection<?>
有r
元素。
答案取决于c.contains(es[r])
的时机检查,在 Collection<?>
的子类中实现:
- 如果
c
是另一个ArrayList<?>
,那么复杂度确实是二次 O(n*r),因为c.contains(es[r])
是 O(r) - 如果
c
是TreeSet<?>
那么时间复杂度就变成了O(n*log2r),因为c.contains(es[r])
是 O(log2r) - 如果
c
是HashSet<?>
那么时间复杂度就变成了O(n),因为hash-basedc.contains(es[r])
是 O(1)
关于java - Java中ArrayList的retainAll和removeAll的时间复杂度是多少。,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53556219/