Почему это работает
- Левее write лежат только встреченные ненулевые числа, в том порядке, в каком их встретил read. Каждое новое встаёт сразу за ними, поэтому порядок не меняется.
- Между write и read лежат только нули. Значит, обмен всегда меняет ноль на число под read: ни одно ненулевое число не теряется и не перепрыгивает другое.
- Когда read дошёл до конца, все ненулевые числа левее write, а во всех ячейках начиная с write — нули.
Сложность
Время O(n): read проходит массив один раз, на каждом шаге — не больше одного обмена. Память O(1): числа переставляются в том же массиве.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗