例如下面的代码:
public int commonTwo(String[] a, String[] b)
{
Set common = new HashSet<String>(Arrays.asList(a));
common.retainAll(new HashSet<String>(Arrays.asList(b)));
return common.size();
}
最佳答案
让我们仔细阅读the code。方法retainAll
继承自AbstractCollection
,并且(至少在OpenJDK中)如下所示:
public boolean retainAll(Collection<?> c) {
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
这里要注意一个大问题,我们遍历
this.iterator()
并调用c.contains
。因此,时间复杂度是n
调用c.contains
,其中n = this.size()
和最多n
调用it.remove()
。重要的是,在另一个
contains
上调用了Collection
方法,因此复杂度取决于另一个Collection
contains
的复杂度。因此,虽然:
Set<String> common = new HashSet<>(Arrays.asList(a));
common.retainAll(new HashSet<>(Arrays.asList(b)));
将为
O(a.length)
,因为HashSet.contains
和HashSet.remove
均为O(1)
(摊销)。如果您要打电话
common.retainAll(Arrays.asList(b));
然后由于
O(n)
上的contains
Arrays.ArrayList
会变成O(a.length * b.length)
-也就是说,通过花费O(n)
将数组复制到HashSet
,您实际上可以更快地调用retainAll
。就空间复杂性而言,
Iterator
不需要额外的空间(除了retainAll
之外),但是在您分配两个实际上完全成熟的HashSet
的新HashMap
实现时,您的调用实际上在空间上非常昂贵。可以注意另外两件事:
HashSet
中的元素分配a
-可以使用便宜的集合,也从中间删除了O(1)
,例如LinkedList
。 (更便宜的内存以及建立时间-未建立哈希表)b.size()
时,所做的修改将丢失。