Задача №4: Move Zeroes

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

Для лучшего понимания задачи рассмотрим несколько примеров:

Пример 1:

• Ввод: nums = [0, 1, 0, 3, 12]
• Вывод: [1, 3, 12, 0, 0]

Пример 2:

• Ввод: nums = [0]
• Вывод: [0]

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

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

1. Мы будем двигать правый указатель right от начала массива к его концу.
2. Если элемент, на который указывает правый указатель, не равен нулю, мы будем его обменивать с элементом, на который указывает левый указатель left. После этого мы увеличим левый указатель.
3. После завершения цикла все ненулевые элементы будут находиться в начале массива, а все нули будут в его конце.

def moveZeroes(nums: List[int]) -> None:
    left = 0
    for right in range(len(nums)):
        if nums[right] != 0 and nums[left] == 0:
            nums[left], nums[right] = nums[right], nums[left]
        if nums[left] != 0:
            left += 1

Разберем каждую строку кода из функции moveZeroes по порядку:

def moveZeroes(nums: List[int]) -> None:

1. def moveZeroes(nums: List[int]) -> None: – Это объявление функции moveZeroes, которая принимает список целых чисел nums в качестве аргумента и не возвращает ничего (возвращает None). Возвращаемый тип указан в аннотации типов (Python type hints).

    left = 0

2. left = 0 – Создается переменная left, которая будет использоваться как левый указатель для перемещения ненулевых элементов.

    for right in range(len(nums)):

3. for right in range(len(nums)):– Это цикл for, который итерируется по всем индексам элементов списка nums. right – это правый указатель, который будет использоваться для перебора элементов массива.

        if nums[right] != 0 and nums[left] == 0:

4. if nums[right] != 0 and nums[left] == 0: – Это условие проверяет, если элемент массива, на который указывает правый указатель (nums[right]), не равен нулю и элемент массива, на который указывает левый указатель (nums[left]), равен нулю.

            nums[left], nums[right] = nums[right], nums[left]

5. nums[left], nums[right] = nums[right], nums[left] – Если условие из предыдущего шага выполняется, происходит обмен значениями между элементами массива на позициях left и right. Это позволяет переместить ненулевой элемент на место первого встреченного нуля.

        if nums[left] != 0:

6. if nums[left] != 0: – После того как был выполнен обмен, проверяется элемент на позиции left. Если он не равен нулю, это означает, что мы уже перенесли ненулевой элемент на его правильное место, и left увеличивается на 1 для указания на следующую позицию в массиве.

            left += 1

7. left += 1 – Увеличение значения left на 1 для перемещения левого указателя на следующий элемент.

Этот код обеспечивает перемещение всех нулевых элементов в конец массива, при этом сохраняя порядок ненулевых элементов.

Сложность алгоритма

Временная сложность данного алгоритма составляет [math]O(n)[/math], где [math]n[/math] – количество элементов в массиве. Мы проходим по массиву только один раз.