Разрешаем дубликаты, но не больше двух!
Уровень сложности: Средняя (Medium)
Теги: Массив, Два указателя, In-place алгоритм
Условие задачи
Дан отсортированный массив целых чисел nums в порядке неубывания.
Удалите дубликаты на месте так, чтобы каждый уникальный элемент встречался не более двух раз.
Относительный порядок элементов должен остаться прежним.
Верните новую длину массива после удаления.
Важно: вы должны выполнить это на месте, используя только O(1) дополнительной памяти.
💡 Модифицированный массив не обязательно должен быть полностью «очищен» — главное, чтобы первые k элементов (где k — возвращаемое значение) были корректными.
Пример 1:
Ввод: nums = [1,1,1,2,2,3]
Вывод: 5, nums = [1,1,2,2,3,_]
Объяснение: Третья '1' удалена, остальные — по два или один раз.
Пример 2:
Ввод: nums = [0,0,1,1,1,1,2,3,3]
Вывод: 7, nums = [0,0,1,1,2,3,3,_]
Анализ задачи
Эта задача — обобщение LeetCode 26 (Remove Duplicates from Sorted Array), где каждое число должно встречаться не более одного раза.
Теперь разрешено до двух копий.
💡 Ключевая идея: два указателя
- i — указатель на позицию, куда мы будем записывать следующий допустимый элемент.
- Проходим по массиву вторым указателем (j — неявно в цикле for).
Поскольку массив отсортирован, все одинаковые элементы идут подряд.
Мы можем безопасно разрешить запись элемента, если:
- Это первый или второй его экземпляр в текущей группе.
Как это проверить?
Так как мы записываем в позицию i, то два элемента назад (на позиции i - 2) не должно быть такого же числа.
Если nums[i - 2] == nums[j], значит, мы уже записали две копии — третья запрещена.
Иначе — можно записывать.
Решение на Java
Комментарии к коду:
- Базовый случай: если длина ≤ 2 — ничего удалять не нужно.
- i = 2: первые два элемента всегда допустимы (даже если они равны).
- Условие nums[j] != nums[i - 2]:i - 2 — позиция, где лежит вторая копия (если есть).
Если текущий элемент отличается от неё — можно записывать. - Мы не меняем порядок и не используем дополнительную память.
💡 Алгоритм работает на месте, и первые i элементов — корректный результат.
Объяснение «словами пятилетнего»
Представь, у тебя есть коробка с наклейками, и они лежат по порядку:
🔴 🔴 🔴 ⚪ ⚪ 🔵 🔵 🔵 🔵
Ты хочешь оставить не больше двух одинаковых наклеек подряд.
Ты берёшь новую коробку (но на самом деле пользуешься той же!) и начинаешь класть наклейки:
- Первую 🔴 — кладёшь.
- Вторую 🔴 — кладёшь.
- Третью 🔴 — не кладёшь, потому что уже две есть!
- Первую ⚪ — кладёшь.
- Вторую ⚪ — кладёшь.
- Первую 🔵 — кладёшь.
- Вторую 🔵 — кладёшь.
- Третью 🔵 — не кладёшь!
- Четвёртую 🔵 — тоже не кладёшь!
В итоге у тебя в начале коробки:
🔴 🔴 ⚪ ⚪ 🔵 🔵
И ты говоришь: «Вот, 6 наклеек — остальные не нужны!»
Твоя программа делает то же самое — только с числами и очень быстро! 😊
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task80_removeDuplicatesFromSortedArraySecond/Solution.java