Алгоритм перемещения нулей в конец списка без изменения порядка остальных элементов

Нельзя просто отсортировать список и развернуть его, так как порядок ненулевых элементов должен остаться прежним.

Пример кода:

def move_zeros(lst):
    write_index = 0  # Индекс для записи ненулевых элементов
    for i, num in enumerate(lst):
        if num != 0:
            lst[write_index] = num  # Записываем ненулевой элемент на текущую позицию write_index
            if write_index != i:    # Если позиции не совпадают, заменяем текущий элемент на 0
                lst[i] = 0
            write_index += 1        # Увеличиваем индекс записи
    return lst

# Пример использования
numbers = [8, 4, 0, 0, 5, 4]
print(move_zeros(numbers))  # Вывод: [8, 4, 5, 4, 0, 0]

Как это работает:

  1. Индекс write_index отслеживает позицию, куда будет записан следующий ненулевой элемент.

  2. Итерация по списку:

    • Если элемент не ноль, он записывается на позицию write_index.

    • Если write_index и текущий индекс i не совпадают (что означает, что между ними были нули), текущий элемент в списке заменяется на 0.

    • Индекс write_index увеличивается только при встрече ненулевого элемента.

  3. Результат: Все нули "сдвигаются" в конец списка, а порядок остальных элементов сохраняется.

Можно этот же алгоритм написать еще элегантнее

 

def move_zeros2(lst):
    tempLst = [i for i in lst if i != 0]
    return tempLst + [0] * (len(lst) -len(tempLst))

print(move_zeros2(list_))

Код занимает 3 строчки, но сложность его выполнения будет выше чем у кода приведенного ранее. Это связано с тем что первый код сортирует списко на месте без использования дополнительных ресурсов. Этот же код создает временный список, что потребует доп ресурсы.