如何在线性时间内从数组列表中删除元素

Question

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

我正在尝试比较数组列表元素上的特定字母，并且需要从数组列表中删除每个较大的字母。这必须在线性时间内完成，因此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 执行此操作。

Answer 1

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

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中的值复制回该列表中，这也需要线性时间。

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

Answer 2

我们可以使用SortedSet来获取元素小于给定字符串的集合，这可以通过使用SortedSet.headSet(String key)方法来实现：

List<String> list = new ArrayList<>();
list.add("d");
list.add("l");
list.add("e");
list.add("z");
list.add("x");
SortedSet<String> set = new TreeSet<>(list);
String x = "f"; //string to compare
List<String> elementsLessThanX = new ArrayList<>(set.headSet("f")); 
System.out.println(elementsLessThanX);

输出：

[d, e]

这绝对不是恒定时间，但它比 O(n^2( 更好。此实现不会修改原始列表。

Answer 3

也许这就是你需要的？

ArrayList<String> b = a.stream().filter(l -> l.compareTo(x) <= 0)
.collect(Collectors.toCollection(ArrayList::new));

Answer 4

成本最低的解决方案是遍历列表一次，同时递增表示与条件匹配的元素数的索引。每次找到元素时，都会在此索引处设置该元素，并且索引递增。最后，您只需要删除此索引右侧的所有内容即可。这样做很便宜，因为在数组列表末尾删除是恒定时间。

public static void main(String[] args) {
List<Integer> list = new ArrayList<>(Arrays.asList(1, 3, 6, 4, 7, 0, 2));
filterLargerElementsInPlace(list, 4, Comparator.naturalOrder());
System.out.println(list); // [1, 3, 0, 2]
}
public static <T> void filterLargerElementsInPlace(List<T> list, T max, Comparator<T> cmp) {
int i = 0;
for (T elem : list) {
if (cmp.compare(elem, max) < 0) {
// mutating the list as we traverse it, but it's safe as i is always less than the current index
list.set(i++, elem);
}
}
while (list.size() > i) list.remove(list.size() - 1);
}

Answer 5

如果你想从列表本身的线性时间内删除元素，而不是创建一个新列表，那么你可以这样做。

int i = 0;
int j = 0;
while (j < A.size()) {
if (A.get(j).compareTo(x) > 0) {
j++;
} else if (i < j) {
A.set(i++, A.get(j++));
} else {
i++;
j++;
}
}
int oldSize = A.size();
int newSize = oldSize - j + i;
A.subList(newSize, oldSize).clear();

这基本上在列表中运行一次，向下移动元素以覆盖需要过滤掉的元素。然后，列表在最后三行中被缩减为大小。