Удаление повторяющихся элементов без использования дополнительной памяти

Условие

Метод устраняет все повторяющиеся значения из списка целых чисел, не прибегая к созданию дополнительных структур данных. Функция должна вернуть новый список, в котором каждый элемент встречается только один раз, при этом расход памяти ограничивается O(1).

Входные данные: [1, 4, 5, 4, 2, 1] Ожидаемый результат: [1, 4, 5, 2]

class Solution {
    public List<Integer> removeDuplicates(List<Integer> numbers) {
        // TODO
    }
}

Ответ

Требования «новый независимый список» и O(1) памяти с учётом результата несовместимы. Если память результата не считается, можно проверять вхождения прямо в выходном ArrayList без дополнительных структур.

public List<Integer> removeDuplicates(List<Integer> numbers) {
    List<Integer> result = new java.util.ArrayList<>();
    for (Integer number : numbers)
        if (!result.contains(number)) result.add(number);
    return result;
}

Сохраняется порядок первых вхождений, время O(n²), память O(k) для результата и O(1) помимо него. Если требуется буквально O(1) дополнительной памяти, нужно изменять исходный список на месте и возвращать его, ослабив требование новой коллекции. HashSet дал бы быстрее, но использовал бы дополнительную память.