Move Zeroes

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

Дан массив чисел. Нужно сдвинуть все нули в конец, а остальные числа оставить в прежнем порядке. Делать это нужно в том же массиве, без второго. Наш пример: [0, 4, 0, 0, 7, 2] → [4, 7, 2, 0, 0, 0].

283 Move ZeroesРазбор · 1×

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

001420304752write
не ноль, уже на местечитаемтолько что поменялисьнулиещё не прочитаны

write = 0: следующее ненулевое число встанет в ячейку 0

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

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

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

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

Сложность

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

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

Решить на LeetCode ↗

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