从 List 中删除第 N 个出现的元素

Question

Java 8 引入了 Lambdas，它允许我们有效地从 List 中删除所有元素。以下内容从 中删除 2 的所有实例myList。

List<Integer> myList;
...
myList.removeIf(x -> x==2);

如果我想删除 N 个元素（在本例中为三个），我将使用for循环。

for (int i = 0; i < 3; i++) {
    myList.remove(Integer.valueOf(2));
}

有没有办法使用 Lambda 从列表中删除指定数量的元素？如果是这样，它是否比for循环代码更有效？

Answer 1

当您重复调用时，remove(Object)您将获得 O(n²) 时间复杂度，从头开始重复搜索（适用于所有List类型），并在列表为 anArrayList或类似列表时重复复制已删除元素之后的元素。

通过使用专用的搜索和删除循环，例如使用 anIterator及其remove方法，可以避免搜索的时间复杂度。但是复制时间复杂度仍然存在，除非您使用removeIf并且列表类使用适当的实现覆盖它（就像ArrayList那样）。

利用这一优势去除n 个匹配项的一种方法是

int n = 3;
int last = IntStream.range(0, myList.size())
    .filter(ix -> myList.get(ix) == 2)
    .limit(n)
    .reduce((a,b) -> b)
    .orElse(-1);
myList.subList(0, last + 1).removeIf(x -> x == 2);

它更复杂，对于小列表，它会更贵。但是，对于时间复杂度很重要的非常大的列表，它将受益于 O(n) 时间复杂度。

请注意，当谓词是简单的匹配操作时，您还可以使用，例如removeAll(Collections.singleton(2))代替removeIf(x -> x == 2)。