java - 想要从另一个列表中存在的列表中删除一些元素

Question

我有一个 list 假设

listA=[679,890,907,780,5230,781]

并想删除另一个存在的一些元素

listB=[907,5230]

最小时间复杂度？

我可以通过使用两个“for 循环”来解决这个问题，这意味着 O(n2) 时间复杂度，但我想将此复杂度降低到 O(nlog(n)) 或 O(n)？
是否可以？

Answer 1

这是可能的 - 如果其中一个列表已排序。假设列表 A 已排序，列表 B 未排序，其各自维度为 M和 N ，从列表 A 中删除所有列表 B 的元素的最小时间复杂度将为 O((N+M)*log(M)) .实现此目的的方法是通过二分查找 - 每次查找列表 A 中的元素都需要 O(log(M))时间，还有N查找(列表 B 中的每个元素一个)。由于需要O(M*log(M))排序 A 的时间，对于大型列表，排序然后删除所有元素更有效，总时间复杂度 O((N+M)*log(M)) .

另一方面，如果您没有排序列表，只需使用 Collection.removeAll ，其时间复杂度为 O(M*N) 在这种情况下。这个时间复杂度的原因是removeAll做(默认情况下)类似于以下伪代码的事情:

public boolean removeAll(Collection<?> other)
    for each elem in this list
        if other contains elem
            remove elem from this list

由于contains时间复杂度为 O(N)对于列表，你最终会做 M迭代，这需要 O(M*N)总共时间。

最后，如果你想最小化 removeAll 的时间复杂度(可能会降低现实世界的性能)您可以执行以下操作:

List<Integer> a = ...
List<Integer> b = ...
HashSet<Integer> lookup = new HashSet<>(b);
a.removeAll(lookup);

对于 b 的错误值，构建 lookup 的时间最多可能需要时间 O(N*log(N)) ，如图here (参见“病态分布的 key ”)。之后，调用 removeAll将采取O(1)对于 contains超过 M迭代，取 O(M)执行的时间。因此，这种方法的时间复杂度为 O(M + N*log(N)) .

所以，这里有三种方法。一个为您提供时间复杂度 O((N+M)*log(M)) ，另一个为您提供时间复杂度 O(M*N) ，最后一个为您提供时间复杂度 O(M + N*log(N)) .考虑到第一种和最后一种方法的时间复杂度相似(因为 log 即使对于大数来说也往往非常小)，我建议使用天真的 O(M*N)对于小输入，最简单的 O(M + N*log(N))用于中型投入。在您的内存使用开始因创建 HashSet 来存储 B 的元素(非常大的输入)而受到影响时，我最终会切换到更复杂的 O((N+M)*log(M))方法。

你可以找到一个 AbstractCollection.removeAll 实现 here .

编辑:
第一种方法不适用于 ArrayLists - 从列表 A 的中间删除需要 O(M)时间，显然。相反，对列表 B ( O(N*log(N)) ) 进行排序，并遍历列表 A，根据需要删除项目。这需要 O((M+N)*log(N)) 时间和优于O(M*N*log(M))使用 ArrayList 时最终得到的结果。不幸的是，该算法的“根据需要删除项目”部分要求您创建数据以将未删除的元素存储在 O(M) 中。 ，因为您无权访问列表 A 的内部数据数组。在这种情况下，最好使用 HashSet 方法。这是因为 (1) O((M+N)*log(N)) 的时间复杂度实际上比 HashSet 方法的时间复杂度更差，并且 (2) 新算法不会节省内存。因此，只有当您有一个带有 O(1) 的列表时才使用第一种方法。删除时间(例如 LinkedList)和 大量的数据。否则，使用 removeAll .它更简单，通常更快，并得到库设计者的支持(例如，ArrayList 有一个 custom removeAll 实现，它允许它使用可忽略的额外内存以线性时间而不是二次时间)。