java - 从 ArrayList 中删除子列表

Question

为简单起见，假设我有一个 ArrayList，其索引只包含一个单位数整数。例如:

6 4 5 6 0 6 3 4 1 6 1 6 0 6 8 3

我想过滤掉所有出现的子列表 6 0 6，这样新列表就变成了:

6 4 5 3 4 1 6 1 8 3

有什么办法吗？使用 ListIterator 似乎对我不起作用，因为我必须共同考虑三个连续的元素，老实说我不确定该怎么做。

这是我实现的方法的框架:

public static void filterList(ArrayList<Integer> list) {
    ListIterator<Integer> iterator = list.listIterator();
    int elem; 
    while (iterator.hasNext()) {
        // Remove any sublist of 6 0 6
    }
}

编辑:同样，为了简单起见，我们假设不会有 60606 或类似的情况。

Answer 1

您可以使用 Collections.indexOfSubList 创建高效简洁的 O(nm) 解决方案:

public static void removeAllSubList(List<?> list, List<?> subList) {
    // find first occurrence of the subList in the list, O(nm)
    int i = Collections.indexOfSubList(list, subList);
    // if found
    if (i != -1) {
        // bulk remove, O(m)
        list.subList(i, i + subList.size()).clear();
        // recurse with the rest of the list
        removeAllSubList(list.subList(i, list.size()), subList);
    }
}

Ideone Demo