Как-то раз на одном из программистских форумов я наткнулся на интересную задачку. Интересна она была тем, что требовалось рекурсивное решение на Java. Мне захотелось разобраться…
Условие
Написать обобщённый метод, который принимает в качестве аргумента коллекцию объектов, обходит её и модифицирует следующим образом:
Если в коллекции встречается только один объект, оставить его как есть.
Если в коллекции идут подряд два одинаковых объекта и более, удалить их все и поместить на это место
null.Метод должен быть рекурсивным.
Примеры:
[1, 2, 2]→[1, null]["dog", "cat", "cat", "fish"]→["dog", null, "fish"][1, 2, 1, 3, 1]→[1, 2, 1, 3, 1]
Процедура или функция?
Очевидно, что настоящий метод (то есть предназначенный для вызова на объекте) нам не понадобится. Хватит статического. По сути это не метод даже, а процедура. Или не процедура? Сложно сказать…
Коллекцию можно обойти только с помощью итератора (под коллекцией понимаем интерфейс java.util.Collection, а не реализацию, например, java.util.ArrayList). Единственная доступная операция изменения – удаление элемента. Причём читать, модифицировать и снова читать нельзя, даже в одном потоке. Соблазнились с помощью одного итератора обходить коллекцию, а с помощью второго менять её? Тоже не получится!
Пусть мы каким-то образом преодолели это ограничение (на самом деле, способ есть, но он не решает принципиальной проблемы, о которой чуть ниже). Мы удалили из исходной коллекции несколько одинаковых идущих подряд элементов. Как мы добавим в коллекцию наш заместитель, то есть null?
Итераторы такой возможности не предоставляют. А метод add() интерфейса Collection нам не поможет. В случае списка, новый элемент добавляется в конец. В случае множества, зависит от реализации. Так, у LinkedHashSet – в конец, у HashSet – неизвестно куда.
Править исходную коллекцию «на лету» не получится. Значит, процедура не годится, нужна функция.
Уточнённое условие
Требуется написать обобщённую функцию, которая принимает в качестве аргумента коллекцию объектов, обходит её и складывает элементы в список таким образом, что:
Если в исходной коллекции встречается только один объект, добавить его в выходной список.
Если в исходной коллекции идут подряд два одинаковых объекта и более, добавить в выходной список одно значение
null.Функция должна быть рекурсивной.
Среди элементов исходной коллекции не должно быть null. Попытка сравнить такое значение с другим потерпит неудачу, а именно приведёт к NullPointerException. Элементы сравниваются посредством метода equals(), а не оператора сравнения. К слову, null в Java – такое же значение, как и все остальные (в отличие от SQL, например).
По отношению к множеству задача вообще не имеет смысла, ибо множество не содержит дубликатов. Множество в качестве исходной коллекции – это вырожденный случай.
Цикл
Решение с циклом проще, чем с рекурсией. Так что рассмотрим сначала его.
LoopSolution.java
import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; import java.util.List; public class LoopSolution { public static <T> List<T> cleanCollection(Collection<T> input) { if (input.size() < 2) return List.copyOf(input); List<T> output = new ArrayList<>(); Iterator<T> tail = input.iterator(); T previousItem = tail.next(); int duplicatesCount = 0; do { T currentItem = tail.next(); if (currentItem.equals(previousItem)) { duplicatesCount++; } else { T mergedItem = merged(duplicatesCount, previousItem); output.add(mergedItem); previousItem = currentItem; duplicatesCount = 0; } } while (tail.hasNext()); T lastItem = merged(duplicatesCount, previousItem); output.add(lastItem); return output; } private static <T> T merged(int duplicatesCount, T previousItem) { return duplicatesCount == 0 ? previousItem : null; } }
Запоминаем первый элемент. Затем идём по коллекции до тех пор, пока не встретится значение, отличное от первого. Заодно подсчитываем число дубликатов. Благодаря счётчику становится ясно, нужно ли объединять одинаковые элементы в null или нет. Добавляем результат в выходной список, берём текущий элемент в качестве первого и мотаем цикл дальше.
Когда цикл завершается, за концом коллекции ничего не остаётся, смена значений не происходит. Этот случай обрабатываем отдельно.
Рекурсия
Рекурсивное решение похоже на циклическое. Просто к той части исходной коллекции, которая осталась после смены значений, функция применяется ещё раз. Последний «кусочек» обрабатывается отдельно, но несколько иначе по сравнению с циклом.
Поскольку рекурсивная функция принимает в качестве аргументов предыдущее значение и итератор, для удобства использования она «завёрнута» в обычную.
RecursiveSolution.java
import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; import java.util.List; import static java.util.Collections.emptyList; import static java.util.Collections.singletonList; import static java.util.Collections.unmodifiableList; public class RecursiveSolution { public static <T> List<T> cleanCollection(Collection<T> input) { if (input.isEmpty()) return emptyList(); Iterator<T> tail = input.iterator(); return cleanTail( tail.next(), tail); } private static <T> List<T> cleanTail(T previousItem, Iterator<T> tail) { if (!tail.hasNext()) return singletonList(previousItem); int duplicatesCount = 0; do { T currentItem = tail.next(); if (currentItem.equals(previousItem)) { duplicatesCount++; } else { List<T> output = new ArrayList<>(); T mergedItem = duplicatesCount == 0 ? previousItem : null; output.add(mergedItem); List<T> remainingItems = cleanTail(currentItem, tail); output.addAll(remainingItems); return unmodifiableList(output); } } while (tail.hasNext()); return singletonList(null); } }
Заключение
Хорошая задача мне попалась: наполовину алгоритмическая, наполовину Java-специфическая. Самое то, чтобы потренироваться.
P.S.
Тесты для обоих решений.
EverySolutionTest.java
import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.Arguments; import org.junit.jupiter.params.provider.MethodSource; import java.util.Collection; import java.util.List; import java.util.stream.Stream; import static java.util.Arrays.asList; import static java.util.Collections.emptyList; import static java.util.Collections.singletonList; import static org.junit.jupiter.api.Assertions.assertEquals; import static org.junit.jupiter.params.provider.Arguments.arguments; public class EverySolutionTest { @ParameterizedTest @MethodSource("data") void loopSolutionTest(List<Integer> expected, List<Integer> input) { Collection<Integer> actual = LoopSolution.cleanCollection(input); assertEquals(expected, actual); } @ParameterizedTest @MethodSource("data") void recursiveSolutionTest(List<Integer> expected, List<Integer> input) { Collection<Integer> actual = RecursiveSolution.cleanCollection(input); assertEquals(expected, actual); } static Stream<Arguments> data() { return Stream.of( arguments( emptyList(), emptyList()), arguments( singletonList("a"), singletonList("a")), arguments( singletonList(null), asList("42", "42")), arguments( asList(1, null), asList(1, 2, 2)), arguments( asList(1, 2, 1, 3, 1), asList(1, 2, 1, 3, 1)), arguments( asList(null, null, null), asList(1, 1, 2, 2, 3, 3)), arguments( asList(2, null, 3), asList(2, 4, 4, 3))); } }
Комментарии (13)
tenzink
28.05.2026 18:52Я, конечно, не спец по java, но решение, вероятно, ужасно: скорее всего упадёт на коллекции с null, подозреваю, что здесь O(n^2), хотя задача, очевидно решается за O(n)
blik13
28.05.2026 18:52Так там в уточнённый условиях
Среди элементов исходной коллекции не должно быть null
tenzink
28.05.2026 18:52Точно. Странное, конечно, ограничение, учитывая, что сами же добавляем null в коллекцию. Но утешение слабое - решение всё равно остаётся кошмарным
flaz14 Автор
28.05.2026 18:52Мне тоже не нравится. Даже с циклом как-то неэлегантно получилось. Не говоря уже про рекурсию. Я всё думал, думал и думал, как бы улучшить…
Пришёл к выводу, что ни сократить код, ни разбить его на функции поменьше не получается. Все эти итераторы, значения прошлые и текущие, счётчик настолько связаны, что если их разнести по маленьким функциям, кода получится даже больше. И не очень понятного.
tenzink
28.05.2026 18:52Это типичная задача на использование пары указателей/итераторов:
один используется для чтения последовательности
второй для записи
Подобная техника очень часто используется, как пример, так делает std::unique (из стандартной библиотеки C++). Сложность получается O(n) без использования дополнительной памяти, и каждый элемент копируется/перемещается не больше одного раза.
Зачем здесь рекурсия, непонятно, разве чтобы посильнее запутать.
qqqqq2
28.05.2026 18:52Рекурсия потому, что новая коллекция может содержать подряд идущие null.
Правда тогда новая коллекция противоречит условию "Среди элементов исходной коллекции не должно быть
null")))Бардак с условиями.
tenzink
28.05.2026 18:52Хотите элегантно? Вот 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 Автор
28.05.2026 18:52Наверное, всё же O(n). Ведь там всего один цикл, а не два вложенных. Счётчик инкрементируется заодно с итерацией по входной коллекции. В рекурсии то же самое, только вместо цикла “хвост” коллекции передаётся в точно такую же функцию.
Кстати, входная коллекция не меняется и при передаче на очередной уровень вложенности не копируется. А вот с результатом наоборот: каждый рекурсивный вызов создаёт новый список, все элементы которого добавляются к списку, созданному предыдущим вызовом. Так что память разбазаривается. А что тут такого? Функциональный подход.
Потребление памяти можно было бы и сократить. Но это совсем другая история. Зарядка должна оставаться зарядкой, а не тренировкой на изнеможение :)
tenzink
28.05.2026 18:52А вот с результатом наоборот: каждый рекурсивный вызов создаёт новый список, все элементы которого добавляются к списку, созданному предыдущим вызовом.
вот тут и прячется O(n^2)
zuzzz
28.05.2026 18:52Значит, процедура не годится, нужна функция.
Годится, результирующую коллекцию можно передавать в параметрах. И это лучше, так как. не требуется создавать новую коллекцию при каждом рекурсивном вызове.
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 не сработал
RodionGork
получается что половина статьи посвящена неправильному условию? :)
задача в том чтобы выяснить в чем заключается задача. такое случается (особенно на собеседованиях) но в качестве статьи про "алгоритмы" выглядит несколько преждевременно, не серчайте пожалуйста :)
P.S. самое безобразное что "подряд идущие" элементы - это понятие примениемое далеко не к любой коллекции. никто не гарантирует что порядок обхода HashSet окажется одним и тем же даже если коллекция содержит те же элементы.
flaz14 Автор
Так и есть, к сожалению. Собственно решение отошло на второй план.
Согласен с Вами, оставил только “Java” и “Программирование”. Просто мне показалось, что эти два хаба слишком общие. Плюс мой стереотип о том, что если что-то делается на Java без сторонних библиотек и фреймворков, то это сто процентов алгоритм. Интересно, у других тоже так?
Над этим я думал и всё бился, как бы это толково расписать, не раздувая, скажем так, теоретическую часть. Но не осилил. Только упомянул, что для множества вообще решать нечего, так как там изначально не может быть двух одинаковых элементов ни рядом, и порознь.
zuzzz
Еще можно по разному интерпретировать “подряд идущие элементы” и рекурсию. Например если данные будут [“dog”, “cat”, “cat”, “dog”] и получившийся результат повторно (рекурсивно?) обработать то в итоге будет [null]