从另一个数组列表中删除一个数组列表元素的最佳方法

tl;dr：

保持简单。用

list.removeAll(new HashSet<T>(listOfElementsToRemove));

相反。

正如Eran在他的答案中已经提到的那样：低性能源于这样一个事实，即泛型实现的伪代码是removeAll

public boolean removeAll(Collection<?> c) {
    for (each element e of this) {
        if (c.contains(e)) {
            this.remove(e);
        }
    }
}

因此，对要删除的元素列表执行的调用将导致 O（n*k） 性能（where 是要删除的元素数，并且是调用该方法的列表中的元素数）。containsnk

天真地，人们可以想象对a的调用也可能具有O（k），并且此实现也将具有二次复杂性。但事实并非如此：您提到列表是特定的实例。该方法的实现是为了委托给一个调用的方法，该方法直接在基础数组上运行，并且不会单独删除元素。this.remove(e)ListArrayListArrayList#removeAllbatchRemove

因此，您所要做的就是确保包含要删除的元素的集合中的查找速度很快 - 最好是 O（1）。这可以通过将这些元素放入 .最后，它可以写成Set

list.removeAll(new HashSet<T>(listOfElementsToRemove));

附注：

恕我直言，Eran的答案有两个主要缺点：首先，它需要对列表进行排序，即O（n*logn） - 而且根本不必要。但更重要的是（显然）：排序可能会改变元素的顺序！如果这根本不是需要的怎么办？

远程相关：实现中还涉及一些其他细微之处。例如，在某些情况下，HashSet removeAll 方法的速度非常慢。虽然这也归结为O（n *n）当要删除的元素存储在列表中时，在这种特殊情况下，确切的行为可能确实令人惊讶。removeAll

好吧，由于检查每个元素是否出现在 中，运行时间与第一个列表的大小乘以第二个列表的大小成正比，这意味着除非两个列表中的一个非常小并且可以被视为“恒定大小”。removeAlltempListtempList2O(N^2)

另一方面，如果对列表进行预排序，然后通过单次迭代（类似于合并排序中的合并步骤）对两个列表进行迭代，则排序将进行迭代，从而获得 的总运行时间为 。下面是两个列表中较大的一个的大小。O(NlogN)O(N)O(NlogN)N

如果可以用排序结构替换列表（可能是 a ，因为你说元素是唯一的），则可以在线性时间实现，因为您不必进行任何排序。TreeSetremoveAll

我还没有测试过它，但是像这样的东西可以工作（假设两者都已排序）：tempListtempList2

Iterator<Integer> iter1 = tempList.iterator();
Iterator<Integer> iter2 = tempList2.iterator();
Integer current = null;
Integer current2 = null;
boolean advance = true;
while (iter1.hasNext() && iter2.hasNext()) {
    if (advance) {
        current = iter1.next();
        advance = false;
    }
    if (current2 == null || current > current2) {
        current2 = iter2.next();
    }
    if (current <= current2) {
        advance = true;
        if (current == current2)
            iter1.remove();
    }
}