例如下面的代码:

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.containsHashSet.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()时,所做的修改将丢失。
  • 10-07 19:14
    查看更多