高效地从 ArrayList 获取子列表

Question

我的问题

---

我有一个包含自定义变量的固定大小ArrayList，尽管ArrayList具有固定大小，但其中很多变量实际上会是null。问题在于我需要返回不包含其中null变量的ArrayList。需要注意的一件重要事情：ArrayList将所有非null项排在前面，然后是所有null项，例如，元素没有混合。例如：[非null，非null，.... null，null，null]

我的解决方法

---

我考虑创建一个for循环，从最后一个索引开始检查ArrayList中的每个元素，以确定它是否为null。 如果为null，则调用此代码：

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

我的问题

---

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

- Jose Lopez

---

.subList方法的时间复杂度为O(1)。它不进行任何复制，非常非常便宜。 - Louis Wasserman

这表明存在严重的设计问题。如果你实际想要的是一个不包含null的可变大小列表，那么为什么要制作一个固定大小的列表并在其中存储null？为什么不至少将第一个null值的索引存储到一个变量中呢？ - JB Nizet

@Rainbolt，我主要是在回应OP问题的最后一句话，它声称“.subList方法很昂贵”。 - Louis Wasserman

Answer 1

您可以使用二分查找的变体，其中自定义比较器为：

• 两个元素都为null/非null？它们相等
• 只有一个元素为null？非null元素“更小”。

您正在寻找第一个null元素。

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

然而，如果您要复制到一个新的列表对象中，则获取不为null的ArrayList子列表将成为所复制的元素的线性时间，因为您必须“触及”每个元素。

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

- amit

---

仅仅改变数组的结束位置而不进行复制/移动就是O(1)--这在某些语言/实现中应该是可能的。那么时间复杂度就是O(logn)？ - Brendan W

@brendan 是的，但据我所知，在Java中特别是需要创建自定义实现。也许ArrayList.removeRange()可以有效地支持这种行为（可能），但它是受保护的方法。 - amit

听起来像是 Java... 哈哈 - Brendan W

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;

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

- Jose Lopez