removeall, удаляет не то что нужно

Question

Есть неупорядоченный список, в котором нужно удалять все одинаковые цифры, стоящие по 3 и более. пример: вход

10 3 3 2 1 1 1 2 2 3 3

По дебагеру после удаления подсписка (1 1 1) становится 10, 3, 3, 2, 2, 3, то есть, удаляется лишняя 2, хотя ее нет в подсписка.

Почему так и как исправить?

for (int i = 0; i < numbers.size() - 3; i++) {
    if (numbers.get(i) == numbers.get(i + 1) && numbers.get(i) == numbers.get(i + 2)) {
        for (int j = i + 3; j < numbers.size(); j++) {
            if (numbers.get(i + 2) == numbers.get(j)) 
                //смотрю 4 и далее может быть цепочка больше 3
                numbers.remove(j); 
            else break;
        }
        List<Object>sublist= numbers.subList(i, i + 3); // тут создаю саблиcт того что удалить хочу
        numbers.removeAll(sublist);
    } else continue;
}

Answer 1

List::removeAll здесь просто напросто не может применяться, так как будут удалены все элементы, входящие в данный подсписок, независимо от их расположения в списке numbers (следует проверить на списке 1, 2, 1, 1, 1, 3, 1 -- будут удалены все единицы!), кроме того, из-за наличия дубликатов в подсписке возникают ложные срабатывания и инкременты счетчика оставшихся элементов при использовании ArrayList::removeAll, для других реализаций списка могут генерироваться ConcurrentModificationException, так как в общем случае в этом методе используется итератор.

Пример реализации ArrayList::removeAll в JDK 8.

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

// ...

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

Как решить?

Поскольку используется итерация по индексам, то удалять совпавшие числа, используя уже знакомый метод remove(int index):

public static void removeNconsecutive(List<Integer> numbers, int n) {
    if (n <= 0) {
        return;
    }
    for (int i = 0; i < numbers.size() - n + 1; i++) {
        int x = numbers.get(i);
        
        boolean toDelete = true;
        for (int j = i + 1; j < Math.min(i + n, numbers.size()); j++) {
            if (x != numbers.get(j)) {
                toDelete = false;
                break;
            }
        }
        
        if (toDelete) {
            // отладочный вывод
            System.out.println("Removing " + x + " at " + i);
            int count = 0;
            while (i < numbers.size() && x == numbers.get(i)) {
                count++;
                numbers.remove(i);
            }
            // отладочный вывод
            System.out.println("Removed " + count + ", remained " + numbers.size() + ": " + numbers);
            i--;
        }
    }
}

Тесты:

List<Integer> numbers = new ArrayList<>(Arrays.asList(10, 1, 3, 3, 2, 1, 1, 1, 2, 2, 3, 3));
removeNconsecutive(numbers, 3);
System.out.println("numbers: "  + numbers);
System.out.println("------");
removeNconsecutive(numbers, 2);
System.out.println("numbers: "  + copy);

Вывод:

Removing 1 at 5
Removed 3, remained 9: [10, 1, 3, 3, 2, 2, 2, 3, 3]
numbers: [10, 1, 3, 3, 2, 2, 2, 3, 3]
------
Removing 3 at 2
Removed 2, remained 7: [10, 1, 2, 2, 2, 3, 3]
Removing 2 at 2
Removed 3, remained 4: [10, 1, 3, 3]
Removing 3 at 2
Removed 2, remained 2: [10, 1]
numbers: [10, 1]

Удаление подсписков может быть более эффективным, чем поэлементное удаление:

public static void removeNconsecutive(List<Integer> numbers, int n) {
    if (n <= 0) {
        return;
    }
    if (n == 1) {
        numbers.clear();
        return;
    }
    for (int i = 0; i < numbers.size() - n + 1; i++) {
        int x = numbers.get(i);
        
        int count = 1;
        for (int j = i + 1; j < numbers.size(); j++) {
            if (x == numbers.get(j)) {
                count++;
            } else break;
        }
        if (count >= n) {
            numbers.subList(i, i + count).clear();
            i--;
        }
    }
}

БЛОГ НА HUSL

removeall, удаляет не то что нужно

Ответы (1 шт):