Move Zeroes

Q: Как переместить нули в конец, не меняя порядок остальных элементов?

Храни индекс write для следующего свободного места в начале и выполняй сканирование с помощью второго индекса. Каждое найденное ненулевое значение меняется местами с элементом на позиции write , а write сдвигается на одну позицию вправо. Значения размещаются в том порядке, в котором ты их находишь, поэтому их взаимный порядок никогда не меняется.

Q: Можно ли решить задачу Move Zeroes с меньшим количеством записей?

Да. Вместо обмена скопируй каждое ненулевое значение в nums[write] , а после прохода заполни все позиции от write до конца нулями. Так каждая позиция будет записана не более одного раза. Также можно пропустить обмен, если read равно write , поскольку значение вернётся на то же место.

ЛегкоДва указателя

+10

Дан массив целых чисел nums. Переместите все нули в конец массива, сохранив порядок остальных значений. Верните переставленный массив, длина которого совпадает с длиной nums.

Функция

moveZeroes(nums: integer-array) → integer-array

numsinteger-array: массив целых чисел для перестановки
Возвращаетinteger-array: nums с ненулевыми значениями в начале, в исходном порядке, а все 0 — в конце

Ограничения

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

Примеры

Ввод: nums = [0, 4, 0, 7, 2]
Вывод: [4, 7, 2, 0, 0]
Пояснение: Значения, не равные 0, — это 4, 7 и 2, и они сохраняют этот порядок в начале. Два нуля занимают последние два места.

Дополнительный вопрос

Можешь вместо этого переместить все 0 в начало, сохранив порядок остальных значений, за один проход и с дополнительной памятью O(1)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Переместить нули в конец — несложно. Сложность в том, чтобы сохранить исходный порядок остальных значений, поэтому нельзя менять каждый 0 местами с последним элементом. Разделите массив на начальную часть, в которой находятся все найденные на данный момент ненулевые значения, и оставшуюся часть. Один индекс проходит по каждому элементу, второй отмечает, куда нужно поместить следующее ненулевое значение, а одного прохода достаточно, чтобы выполнить задачу на месте.

Скопируйте ненулевые значения

Идея

Создай новый массив. Пройди по nums и скопируй каждое значение, которое не равно 0, в том порядке, в котором ты его встречаешь. Затем добавь нули, пока длина нового массива не станет такой же, как у nums. Количество добавленных нулей равно количеству пропущенных элементов.

Для [0, 4, 0, 7, 2] на этапе копирования получится [4, 7, 2], а два нуля дадут [4, 7, 2, 0, 0]. Порядок сохраняется, потому что ты копируешь значения в том порядке, в котором их читаешь.

Каждый элемент читается один раз и записывается один раз, поэтому временная сложность — O(n). Второй массив требует O(n) памяти, от которой позволяет избавиться следующий подход.

Алгоритм

Создай пустой массив результата.
Для каждого значения в nums добавь его в результат, если оно не равно 0.
Добавляй нули, пока в результате не будет столько же элементов, сколько в nums.
Верни результат.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

Два указателя, обмен элементов на месте

Идея

Используйте два индекса. read проходит по каждому элементу слева направо. write указывает, где должно находиться следующее ненулевое значение. После каждого шага выполняются два условия: все элементы перед write — это уже встреченные ненулевые значения в исходном порядке, а все элементы от write до read — это 0.

Когда nums[read] не равен 0, поменяйте его местами с nums[write] и сдвиньте write на один шаг вправо. Значение, которое оказывается на месте read, — это 0 из зоны нулей либо то же самое значение, если оба индекса равны. Ненулевые значения перепрыгивают только через нули, никогда — друг через друга, поэтому их порядок сохраняется.

Для [0, 4, 0, 7, 2]: 4 с индексом 1 меняется местами с элементом по индексу 0, в результате получается [4, 0, 0, 7, 2]. 7 с индексом 3 меняется местами с элементом по индексу 1, в результате получается [4, 7, 0, 0, 2]. 2 с индексом 4 меняется местами с элементом по индексу 2, в результате получается [4, 7, 2, 0, 0]. Один проход и без второго массива: время O(n), память O(1).

Алгоритм

Установи write в 0.
Перемещай read от первого индекса к последнему.
Если nums[read] не равно 0, поменяй местами nums[read] и nums[write], затем увеличь write на 1.
Верни nums.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

Ловушки и крайние случаи

Обычные ошибки либо нарушают порядок остальных значений, либо пропускают элементы.

Замена каждого 0 последним элементом перемещает нули, но перемешивает остальные элементы: [0, 4, 7] становится [7, 4, 0].
Удаление нулей из массива, пока индекс проходит по нему, приводит к пропуску элементов. В [0, 0, 5] удаление элемента с индексом 0 сдвигает второй 0 на индекс 0, а цикл переходит к индексу 1. Каждое удаление также сдвигает остальные элементы массива, из-за чего цикл работает за O(n²).
Проверяйте x != 0, а не x > 0. Отрицательные значения — не нули: [-1, 0, -2] должно превратиться в [-1, -2, 0], но при проверке x > 0 версия с копированием возвращает [0, 0, 0].
Массив без нулей или состоящий только из нулей должен остаться без изменений. В версии с обменом read и write остаются равными до первого 0, поэтому эти обмены ничего не меняют.
В Lua и R индексация массивов начинается с 1, поэтому write тоже начинается с 1.

Частые вопросы3

Какова временная сложность Move Zeroes?

O(n). Оба подхода считывают каждый элемент один раз. Копирование ненулевых значений в новый массив требует дополнительной памяти O(n), а обмен с двумя указателями выполняется внутри массива и требует дополнительной памяти O(1).

Как переместить нули в конец, не меняя порядок остальных элементов?

Храни индекс write для следующего свободного места в начале и выполняй сканирование с помощью второго индекса. Каждое найденное ненулевое значение меняется местами с элементом на позиции write, а write сдвигается на одну позицию вправо. Значения размещаются в том порядке, в котором ты их находишь, поэтому их взаимный порядок никогда не меняется.

Можно ли решить задачу Move Zeroes с меньшим количеством записей?

Да. Вместо обмена скопируй каждое ненулевое значение в nums[write], а после прохода заполни все позиции от write до конца нулями. Так каждая позиция будет записана не более одного раза. Также можно пропустить обмен, если read равно write, поскольку значение вернётся на то же место.

def moveZeroes(nums):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

nums = [0, 4, 0, 7, 2]

Ожидаемый вывод

[4, 7, 2, 0, 0]