Remove Duplicates from Sorted Array II

Средняя№80в одну сторону

Дан массив чисел, отсортированный по возрастанию. Нужно переписать его на месте так, чтобы каждое число встречалось не больше двух раз, не меняя порядок, и вернуть, сколько чисел осталось; что лежит дальше, неважно. Наш пример: [1, 1, 1, 2, 2, 3, 3, 3, 3] → 6, и массив начинается с [1, 1, 2, 2, 3, 3].

80 Remove Duplicates from Sorted Array IIРазбор · 1×

Пример: [1, 1, 1, 2, 2, 3, 3, 3, 3]. read проходит каждое число, write отмечает, куда встанет следующее оставленное. Число оставляем, если оно не равно nums[write - 2].

011121324253637383write
оставлены: ответ на данный моментnums[read] и nums[write - 2], с которым его сравниваемсюда только что скопировалипропущены или остаткиещё не прочитаны

write = 0: пока ничего не оставили

01/33
сначала · назад · пуск · шаг
Скорость
1function removeDuplicates(nums):
2 write = 0
3 for read from 0 to len(nums) - 1:
4 if write < 2 or nums[read] != nums[write - 2]:
5 nums[write] = nums[read]
6 write = write + 1
7 return write
состояние
write
0
read
–
nums[read]
–
nums[write - 2]
–
nums
[1, 1, 1, 2, 2, 3, 3, 3, 3]
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Всё левее write — уже ответ, и он отсортирован. Если nums[read] равно nums[write - 2], то оно равно и всему между ними: ответ уже кончается двумя такими числами, и третье лишнее.
  2. Соседа мало: равные соседи говорят только, что число повторяется, а не сколько раз его уже оставили. В 1, 1, 1 вторая и третья единица рядом с соседом выглядят одинаково, но убрать нужно только третью. nums[write - 2] считает за нас.
  3. Не больше k раз: первые k чисел оставляем, а сравниваем с nums[write - k]. При k = 1 это задача 26, Remove Duplicates from Sorted Array.

Сложность

Время O(n): read проходит массив один раз, на каждом шаге — одно сравнение и не больше одного копирования. Память O(1): массив переписываем на месте, сбоку только два индекса.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.