时间戳

首页 > 解决方案 > 如何在线性时间内从arraylist中删除元素

java - 如何在线性时间内从arraylist中删除元素

问题描述

很好的建议，但其中一些是不允许的（作为流），是非常有限的任务。Leo 的算法正是我一直在寻找的东西。

我正在尝试比较 arraylist 元素上的特定字母，并且需要从 arraylist 中删除每个更大的字母。这必须在线性时间内完成，因此remove()不是一种选择。我该怎么做？

int deleted = 0;
int n = 0;

while (n < A.size()) {
    if (A.get(n).compareTo(x) > 0) {
        //removing here
        removed = removed + 1;
    }
    n++;
}

return removed;

A是一个带有随机字母的数组列表，x也是一个随机字母。我需要删除每个A大于给定x字母的元素。Remove() 不是一个选项，因为我需要在线性时间内而不是 n^2 中执行此操作。

标签： javaarraylisttime-complexity

解决方案

您可以在线性时间内将元素添加到另一个列表中。例如：

ArrayList<Integer> result = new ArrayList<Integer>();
for(int n = 0; n < A.size(); n++) {
    if(A.get(n).compareTo(x) <= 0) {
        result.add(A.get(n));
    }
}
return result;

或@Dici 所说的流：

A.stream().filter(n -> n.compareTo(x) <= 0).collect(Collectors.toList());

您可以稍后交换列表，或清除原始列表，然后从result该列表的后面复制值，这也需要线性时间。

尽管使用另一种数据结构来存储数据也可能是有益的。

推荐阅读