Задача №3850. Сжатие списка

Question

Дан список целых чисел. Требуется “сжать” его, переместив все ненулевые элементы в левую часть списка, не меняя их порядок, а все нули - в правую часть. Порядок ненулевых элементов изменять нельзя, дополнительный список использовать нельзя, задачу нужно выполнить за один проход по списку. Распечатайте полученный список.

Входные данные:

Вводится список чисел. Все числа списка находятся на одной строке.

Выходные данные:

Выведите ответ на задачу.

Мой код:

s = input().split()
for i in reversed(range(len(s))):
    if s[i] == '0':
        s.append(s.pop(i))
print(*s)

Однако на одном из тестов мне пишут "Превышено максимальное время работы". Что не так?

Answer 1

Попробуйте такой код.

snz - это флаг, который значит, что нужно искать ненулевое значение для свопа. j - индекс элемента, с которым надо сделать своп ненулевому элементу. То есть при появлении первого элемента с нулевым значением происходит сдвиг всех ненулевых элементов именно к индексу j, после все нулевые значения просто пропускаются, а для ненулевых происходит своп на индекс с j и увеличение этого индекса.

s = list(map(int, input().split()))
snz = False
i=0
while (i<len(s)):
    if s[i]==0 and not snz:
        snz=True
        j=i
    while s[i]==0 and i < len(s)-1:
        i+=1
    if snz and s[i]!=0:
        s[j],s[i]=s[i],0
        j += 1
    i+=1
print(*s)

Answer 2

Наверное, в ответе xmikex имелось в виду что-то похожее на мой ответ, но я не совсем разобрался в его коде, мой код мне кажется гораздо понятнее, я понимаю, что он делает.

s = list(map(int, input().split()))

j = len(s) - 1
for i in range(len(s)):
    if s[i] == 0:
        while j > i:
            if s[j] == 0:
                j -= 1
            else:
                s[i], s[j] = s[j], s[i]
                j -= 1
                break
        else:
            break
print(*s)

Просто храним справа индекс последнего элемента, который может быть не нулём. А слева идём по списку и когда находим подходящий нулевой элемент для обмена, то ищем справа наоборот ненулевой элемент - и меняем эти элементы местами. Таким образом первый и второй индекс постепенно сходятся в одну точку, получается ровно один проход по списку. И список используется один. Из списка при этом нет удалений и нет вставок, есть только обмен, поэтому скорость не страдает.

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

Answer 3

Ваше решение медленное, так как вы удаляете элементы из середины массива. Это операция медленная - все элементы после удаляемого нужно сдвинуть на одну позицию влево. Это долго если массив длинный. Говоря высоким слогом ваше решение работает за квадрат. А можно сделать решение за линию.

Классическое решение задачи состоит в том что по массиву a бегут два индекса i и j. i перебирает все элементы, j от него отстает на каждом нуле. Если элемент не нуль, то он копируется с позиции i в позицию j.

Когда цикл окончился, все ненулевые элементы собрались в начале массива. В конце мусор, который мы заполняем нулями:

def move_zeros_2(a):
    j = 0
    for i in range(len(a)):
        if a[i] != '0':
            a[j] = a[i]
            j += 1
    for k in range(j, len(a)):
        a[k] = '0'

На Питоне не принято делать циклы по range(len(...)). Код ниже лучше соответствует языку:

def move_zeros_3(a):
    j = 0
    for v in a:
        if v != '0':
            a[j] = v
            j += 1
    for k in range(j, len(a)):
        a[k] = '0'

БЛОГ НА HUSL

Задача №3850. Сжатие списка

Ответы (3 шт):