Remove Duplicates from Sorted Array

Лёгкая№26в одну сторону

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

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

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

01112233435365write
уникальные, уже на местечитаемсюда только что записалиповторы и остаткиещё не прочитаны

nums[0] = 1 — первое число, значит, новое: оно остаётся, а следующее новое встанет в ячейку 1

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

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

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

  1. Массив отсортирован, поэтому равные числа стоят подряд. Повтор может идти только сразу за своим числом, значит, хватает сравнения с последним записанным: дальше назад смотреть не нужно.
  2. Левее write лежит каждое встреченное число по одному разу, по возрастанию. Новое число больше их всех, поэтому встаёт сразу за ними, в nums[write].
  3. Когда число записывается, write никогда не правее read, поэтому запись затирает только уже прочитанную ячейку. Ни одно непрочитанное число не теряется.

Сложность

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

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

Решить на LeetCode ↗

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