Перемещение списка Python и внесение изменений на месте

Question

Моя задача - удалить все экземпляры одного конкретного элемента ('6' в этом примере) и переместить их в конец списка. Требование состоит в том, чтобы пройти список, вносящий изменения в строке (не создавая дополнительных списков).

Пример ввода: [6,4,6,2,3,6,9,6,1,6,5] Пример вывода: [4,2,3,9,1,5,6,6 , 6,6,6]

до сих пор я был в состоянии сделать это только за счет дополнительных списков (ломка требования задания), так что рабочий код не допускается:

def shift_sixes(nums): 
    b = [] 
    c = 0 
    d = [] 

    for i in nums: 
    if i == 6: 
     b.insert(len(nums),i) 
    elif i != 6: 
     c = c +1 
     d.insert(c,i) 

    ans = d + b 
    return ans 

Я ve также попробовал list.remove() и list.insert(), но столкнулся с проблемой индексирования (который перемещается, когда I insert() затем переместите элемент в конец): Например -

a = [6,4,6,2,3,6,9,6,1,6,5] 
    def shift_sixes(nums): 
    for i in nums: 
     if i == 6: 
      nums.remove(i) 
      nums.insert(nums[len(nums)-1], 0) 
     elif i != 0: 
      i 
shift_sixes(a) 

Кроме того, я пытался использовать функцию перечисления() следующим образом, но возникают проблемы с правой стороны от Ь [IDX] распайка линия:

for idx, b in enumerate(a): 
    a[idx] = ??? 

Читала другие записи StackOverflow here, here и here, но они не занимаются перемещением элемента на один конец.

Поблагодарили бы за любую помощь в этой проблеме. Большое спасибо.

---

EDIT @eph - спасибо. это действительно элегантный ответ. Я уверен, что он выполнит мое требование «нет нового списка»? Я обязательно намереваюсь больше узнать о лямбда и ее использовании. @falsetru - спасибо за напоминание о комбинации append/pop (которую я пытался сделать в своем исходном запросе через list.remove() и list.insert() @ tdelaney - также спасибо. Как-то ваш ответ ближе всего к тому, что я пытался, но, похоже, он не прошел тест на [0, 0, 5].

Answer 1

Итерация списка в обратном направлении, pop элемент, если он 6, а затем append он.

xs = [6,4,6,2,3,6,9,6,1,6,5] 

for i in range(len(xs)-1, -1, -1): # 10 to 0 
    if xs[i] == 6: 
     xs.append(xs.pop(i)) 

Answer 2

Почему бы не попробовать что-то вроде этого?

В принципе, подход состоит в том, чтобы сначала подсчитать количество значений. Если 0, то возвращается (поскольку Python создает ValueError, если метод list.index вызывается для элемента, не входящего в список).

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

Затем мы можем скомбинировать list.pop/list.append, чтобы затем пройти список до тех пор, пока все нужные значения не появятся в конце списка.

def shift_value(lst, value): 
    counts = lst.count(value)  # 5 
    if not counts: 
     return lst 

    value_index = len(lst) - counts 
    index = lst.index(value) 
    while index != value_index: 
     lst.append(lst.pop(index)) 
     index = lst.index(value) 
    return lst 

lst = [6,4,6,2,3,6,9,6,1,6,5] 
print(shift_value(lst, 6)) 

EDIT: Это ужасно неэффективно, лучший ответ, предложенный выше. Для этого требуется время O (n^2), а не O (n).

Answer 3

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

На самом деле, вопрос может быть сделано разными способами, такими как:

>>> a.sort(key = lambda i: i == 6) 
>>> a 
[4, 2, 3, 9, 1, 5, 6, 6, 6, 6, 6] 

Answer 4

Ключевым термином здесь является "In Line". То, как вы это делаете, это перемещение num[i] = num[i+1] для каждого i в конец списка.

def shift_sixes(num): 
    for i, val in enumerate(num): 
     if val == 6: 
      # shift remaining items down 
      for j in range(i,len(num)-1): 
       num[j] = num[j+1] 
      # add 6 at the end 
      num[-1] = 6 
    return num 

print(shift_sixes([1,9,4,6,2,7,8,6,2,2,6])) 
print(shift_sixes([1,2,3])) 
print(shift_sixes([6])) 
print(shift_sixes([3])) 

Answer 5

Использование двух бегунов. Сначала от начала до конца, проверяя 6 секунд, второй от конца до фронта, указывающего на последний элемент, который не является 6. Продолжайте менять (a[i+1], a[i] = a[i], a[i+1]) до тех пор, пока они не соберутся.

Поймать: Это не стабильно, как в стабильном виде. Но я не вижу этого в качестве требования.

Попробует написать рабочий код, когда перед интерпретатором python с клавиатурой.

Answer 6

В случае, если вам нужен стабильный вид (т.е. порядок элементов, которые не 6 должны оставаться такими же), то решение:

def move_to_end(data, value): 
    current = 0 # Instead of iterating with for, we iterate with index 
    processed = 0 # How many elements we already found and moved to end of list 
    length = len(data) # How many elements we must process 
    while current + processed < length: # While there's still data to process 
     if data[current] == value: # If current element matches condition 
      data.append(data.pop(current)) # We remove it from list and append to end 
      processed += 1 # Our index remains the same since list shifted, but we increase number of processed elements 
     else: # If current element is not a match 
      current += 1 # We increase our index and proceed to next element 

if __name__ == '__main__': 

    print 
    print 'Some testing:' 
    print 

    for test_case in (
     [1, 9, 4, 6, 2, 7, 8, 6, 2, 2, 6], # Generic case 
     [6, 6, 6, 6], # All items are 6 
     [1, 7], # No items are 6 
     [], # No items at all 
    ): 
     print 'Raw:', test_case 
     move_to_end(test_case, 6) 
     print 'Becomes:', test_case 
     print 

Обратите внимание, что это решение сохраняет порядок не только не -обновляющие элементы, но и соответствующие элементы. Например, если вы измените условие проверки с «равным 6» на «четное число», все элементы, соответствующие этому условию, будут перемещены в конец списка, сохраняя при этом свой порядок между собой.

Answer 7

Почему бы не сохранить его простым?

a = [6,4,6,2,3,6,9,6,1,6,5] 
def shift_sixes(nums): 
    for i in range(0,len(nums)): 
     if nums[i] == 6: 
      nums.append(nums.pop(i)) 

>>> shift_sixes(a) 
>>> a 
[3, 9, 1, 5, 2, 4, 6, 6, 6, 6]