283. Move Zeroes

LeetCode задача

Задача

Дан целочисленный массив nums. Нам необходимо переместить все 0 в конец массива, сохраняя относительный порядок ненулевых элементов.

Примечание: вы должны сделать это на месте, без создания копии массива.

Подсказки

Используйте два указателя: один будет указывать на текущий элемент, а другой будет указывать на первое место в массиве, куда можно поместить ненулевой элемент.

Подход

Мы можем использовать два указателя: один для прохода по массиву и другой для отслеживания местоположения, куда следует поместить следующий ненулевой элемент. Этот метод позволяет нам сделать минимальное количество операций и изменений в массиве.

Алгоритм

1. Инициализируем два указателя на начало массива.
   1. Первый указатель - это индексы массива. Второй с начальным значением 0,
2. Используя первый указатель, проходим по массиву.
   1. Если текущий элемент не равен нулю, помещаем его на позицию, указанную вторым указателем (меняем значения местами), и перемещаем второй указатель на одну позицию вперед.
3. После завершения прохода, все числа после второго указателя должны быть установлены в 0.

Решение

def moveZeroes(nums: List[int]) -> None:
    pos = 0                                          # Указатель для ненулевых элементов

    for i in range(len(nums)):
        if nums[i] != 0:                             # Если текущий элемент не 0, 
            nums[i], nums[pos] = nums[pos], nums[i]  # меняем его местами с элементом на позиции pos
            pos += 1