有效地从 ArrayList 中获取子列表

Question

我的问题

我有一个包含自定义变量的固定大小的 ArrayList。尽管 ArrayList 具有固定大小，但有时它们中的很多实际上都是空的。问题是我需要 return ArrayList 里面没有空变量。 需要注意的一件重要事情： ArrayList 将首先拥有它的所有非空项，然后是所有空值在它们下面，例如，元素没有混合。示例：[非空，非空，....空，空，空]

我的解决方法

我想创建一个 for 循环来检查（从最后一个索引到第一个索引）ArrayList 中的每个元素以确定它是否为 null。如果为空，那么我将调用此代码：

for (i = size-1; i >=0 ; i--) {
    groupList = new ArrayList<>(groupList.subList(0, i));
}

我的问题

如果 ArrayList 太大，这个方法可能会特别慢（或者不是？）。我想知道是否存在更好、性能更友好的解决方案。据我所知，.subList 方法很昂贵。

Answer 1

您可以使用 binary search 的变体，其中您的自定义比较器是：

两个元素都是null/not null？他们是平等的
只有一个元素为空？ none 空值是 "smaller".

您正在查找第一个空元素。

这将花费 O(logn) 时间，其中 n 是数组的大小。

但是，取 ArrayList 的子列表，即 none null（假设您要将其复制到新的列表对象），将是复制元素的线性时间，因为您必须 "touch" 他们中的每一个。

总时间复杂度为 O(logn + k)，其中 k 是非空元素的数量，n 是数组的大小。

Answer 2

根据您的所有出色建议，我修改了原始方法，以便我可以获取 最后（第一个）空项位置 并仅调用 .subList 方法一次。这是：

int lastNullIndex = size - 1;

for (i = lastNullIndex; i >= 0; i--) {
    if (null == groupList.get(i)) {
        lastNullIndex = i;
    } else {
        break;
    }
}

groupList = new ArrayList<>(groupList.subList(0, lastNullIndex));
return groupList;

如果您认为可以进一步修改它以获得更好的性能，请告诉我们。

有效地从 ArrayList 中获取子列表

Get a sublist from an ArrayList efficiently

java

algorithm

arraylist

time-complexity