Зарядка для джависта

[RodionGork]

принимает в качестве аргумента коллекцию объектов ... и модифицирует 

...

принимает в качестве аргумента коллекцию объектов ... и складывает элементы в список 

получается что половина статьи посвящена неправильному условию? :)

задача в том чтобы выяснить в чем заключается задача. такое случается (особенно на собеседованиях) но в качестве статьи про "алгоритмы" выглядит несколько преждевременно, не серчайте пожалуйста :)

Если в исходной коллекции идут подряд два одинаковых объекта 

P.S. самое безобразное что "подряд идущие" элементы - это понятие примениемое далеко не к любой коллекции. никто не гарантирует что порядок обхода HashSet окажется одним и тем же даже если коллекция содержит те же элементы.

[flaz14]

получается что половина статьи посвящена неправильному условию? :)

Так и есть, к сожалению. Собственно решение отошло на второй план.

в качестве статьи про “алгоритмы” выглядит несколько преждевременно, не серчайте пожалуйста :)

Согласен с Вами, оставил только “Java” и “Программирование”. Просто мне показалось, что эти два хаба слишком общие. Плюс мой стереотип о том, что если что-то делается на Java без сторонних библиотек и фреймворков, то это сто процентов алгоритм. Интересно, у других тоже так?

P.S. самое безобразное что “подряд идущие” элементы - это понятие примениемое далеко не к любой коллекции

Над этим я думал и всё бился, как бы это толково расписать, не раздувая, скажем так, теоретическую часть. Но не осилил. Только упомянул, что для множества вообще решать нечего, так как там изначально не может быть двух одинаковых элементов ни рядом, и порознь.

[zuzzz]

Еще можно по разному интерпретировать “подряд идущие элементы” и рекурсию. Например если данные будут [“dog”, “cat”, “cat”, “dog”] и получившийся результат повторно (рекурсивно?) обработать то в итоге будет [null]

[tenzink]

Я, конечно, не спец по java, но решение, вероятно, ужасно: скорее всего упадёт на коллекции с null, подозреваю, что здесь O(n^2), хотя задача, очевидно решается за O(n)

[blik13]

Так там в уточнённый условиях

Среди элементов исходной коллекции не должно быть null

[tenzink]

Точно. Странное, конечно, ограничение, учитывая, что сами же добавляем null в коллекцию. Но утешение слабое - решение всё равно остаётся кошмарным

[flaz14]

Мне тоже не нравится. Даже с циклом как-то неэлегантно получилось. Не говоря уже про рекурсию. Я всё думал, думал и думал, как бы улучшить…

Пришёл к выводу, что ни сократить код, ни разбить его на функции поменьше не получается. Все эти итераторы, значения прошлые и текущие, счётчик настолько связаны, что если их разнести по маленьким функциям, кода получится даже больше. И не очень понятного.

[tenzink]

Это типичная задача на использование пары указателей/итераторов:

• один используется для чтения последовательности

• второй для записи

Подобная техника очень часто используется, как пример, так делает std::unique (из стандартной библиотеки C++). Сложность получается O(n) без использования дополнительной памяти, и каждый элемент копируется/перемещается не больше одного раза.

Зачем здесь рекурсия, непонятно, разве чтобы посильнее запутать.

[qqqqq2]

Рекурсия потому, что новая коллекция может содержать подряд идущие null.

Правда тогда новая коллекция противоречит условию "Среди элементов исходной коллекции не должно быть null")))

Бардак с условиями.

[tenzink]

Хотите элегантно? Вот python: O(n), работает с None, не in-place и можно было написать ещё пооптимальней:

#! /usr/bin/python3

from itertools import groupby

def replace_duplicates_with_nones(lst):
    return [val if sum(1 for _ in group) == 1 else None for val, group in groupby(lst)]

if __name__ == "__main__":
    print(replace_duplicates_with_nones([1, 2, 2, 3, 4, 4, 4, 5, 2, 2]))
    print(replace_duplicates_with_nones([1, 2, 3]))
    print(replace_duplicates_with_nones([]))
    print(replace_duplicates_with_nones([None, None]))

Хотите классическое решение через пару итераторов? Вот на C++, O(n), заменяет in-place без доп памяти, работает с None:

#include <iostream>
#include <vector>
#include <optional>
#include <algorithm>

template <typename ForwardIt>
ForwardIt replaceDuplicatesWithNull(ForwardIt first, ForwardIt last) {
    if (first == last) {
        return last;
    }

    ForwardIt write = first; 
    ForwardIt head = first;   

    while (head != last) {
        ForwardIt next_group = std::find_if(head, last, [&](const auto& val) {
            return val != *head;
        });

        if (std::next(head) == next_group) {
            if (write != head) {
                *write = std::move(*head);
            }
        } else {
            *write = std::nullopt;
        }
        
        ++write;
        head = next_group;
    }

    return write;
}

int main() {
    std::vector<std::optional<int>> data = {1, 2, 2, 3, 4, 4, 4, 5, 2, 2};
    
    auto new_end = replaceDuplicatesWithNull(data.begin(), data.end());
    data.erase(new_end, data.end());

    for (const auto& val : data) {
        std::cout << (val ? std::to_string(*val) : "null") << " ";
    }
    std::cout << std::endl;
}

[flaz14]

Наверное, всё же O(n). Ведь там всего один цикл, а не два вложенных. Счётчик инкрементируется заодно с итерацией по входной коллекции. В рекурсии то же самое, только вместо цикла “хвост” коллекции передаётся в точно такую же функцию.

Кстати, входная коллекция не меняется и при передаче на очередной уровень вложенности не копируется. А вот с результатом наоборот: каждый рекурсивный вызов создаёт новый список, все элементы которого добавляются к списку, созданному предыдущим вызовом. Так что память разбазаривается. А что тут такого? Функциональный подход.

Потребление памяти можно было бы и сократить. Но это совсем другая история. Зарядка должна оставаться зарядкой, а не тренировкой на изнеможение :)

[tenzink]

А вот с результатом наоборот: каждый рекурсивный вызов создаёт новый список, все элементы которого добавляются к списку, созданному предыдущим вызовом.

вот тут и прячется O(n^2)

[zuzzz]

Значит, процедура не годится, нужна функция.

Годится, результирующую коллекцию можно передавать в параметрах. И это лучше, так как. не требуется создавать новую коллекцию при каждом рекурсивном вызове.

    public static <T> List<T> cleanCollection(Collection<T> input) {
        if (input.isEmpty())
            return emptyList();
        Iterator<T> tail = input.iterator();
        List<T> output = new ArrayList<>(input.size());
        cleanTail(tail.next(), tail, output);
        return output;
    }

    private static <T> void cleanTail(T previousItem, Iterator<T> tail, List<T> output) {
        if (!tail.hasNext()) {
            output.add(previousItem);
            return;
        }
        int duplicatesCount = 0;
        do {
            T currentItem = tail.next();
            if (currentItem.equals(previousItem)) {
                duplicatesCount++;
            } else {
                T mergedItem = duplicatesCount == 0 ? previousItem : null;
                output.add(mergedItem);
                cleanTail(currentItem, tail, output);
                return;
            }
        } while (tail.hasNext());
        output.add(null);
    }

Извините, не смог засунуть код под спойлер. Тег spoiler не сработал