Блог

Я работаю над проблемой, которая будет принимать этот ввод:

 [1, 0, 2, 3, 0, 4, 5, 0]
  

И выведите это:

 [1, 0, 0, 2, 3, 0, 0, 4]
  

Моя функция обнаруживает нули, и когда ноль является i-м элементом списка, i 1 он также становится нулем, а остальная часть списка сдвигается, чтобы освободить для него место. Элементы в конце списка выталкиваются, чтобы освободить место.

Я смог сделать это с помощью двух for циклов, но это имеет O(n^2) место, и я хочу это сделать O(n) . Я придумал это:

 new = [0] * len(arr)
zeroes = 0
d = 0
  

Я создаю второй список нулей, zeroes подсчитывает список нулей и d является индексом для копирования для второго списка. Массив, который я использую, является входом в функцию и называется arr .

Сначала я считаю нули:

 for i in range(len(arr)):
    if arr[i] == 0:
        zeroes =1  
  

Затем я копирую. Я проверяю по индексу, что значение равно нулю, и если это так, я пропускаю d-й и d 1-й элемент.

 for i in range(len(arr)-zeroes):
    if arr[i] == 0:
        d =1
    else:
        new[d] = arr[i]
    d =1
  

Однако для:

 [1, 0, 2, 3, 0, 4, 5, 0]
  

Результат:

 [1, 0, 0, 2, 3, 0, 0, 0]
  

Я не уверен, почему последний элемент не меняется.

Вот более простое решение, которое по-прежнему является O (n):

 a = [1,0,2,3,0,4,5,0]
b = []
for i in a:
    b.append(i)
    if i == 0:
        b.append(0)
b = b[:len(a)]
  

Значение b будет

 [1, 0, 0, 2, 3, 0, 0, 4]