Remove Element

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

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

27 Remove ElementРазбор · 1×

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

041124344253write
оставлены: ответ на данный моментчитаемсюда только что скопировалиравно val: пропущеноуже скопировано левееещё не прочитаны

write = 0: первое оставленное число встанет в ячейку 0

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

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

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

  1. Левее write лежат ровно те числа, которые уже оставили: каждое число, не равное val, копируется в write, и write сдвигается. Значит, всё левее write — уже готовая часть ответа.
  2. write сдвигается не больше раза за шаг read, поэтому никогда не обгоняет read. Копия затирает только ячейку, которую read уже посмотрел: ни одно число не теряется до проверки.
  3. Когда read дошёл до конца, каждое число проверено один раз. write — сколько чисел осталось, и они лежат в первых write ячейках.

Сложность

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

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

Решить на LeetCode ↗

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