Как поменять серию c номером k повторяющихся элементов в списке c последней серией в списке?

#python #алгоритм

Пусть k = 2

Скажем, есть список:  

array = [2,2,4,5,5,7,1,6,9,9,2]


Необходимо сделать так, чтобы было: 

array = [2,2,4,9,9,7,1,6,5,5,2]

    

Ответы

Ответ 1

Алгоритм:


найти позиции k-ой  и последней серий, состоящих из повторяющихся элементов
поменять их местами




from itertools import groupby

# 1. find the k-th and the last group with repeated items
pos = 0  # position in the array
repeated_group_count = 0
for _, group in groupby(array):
    n = len(list(group))
    pos += n
    if n > 1:  # found group with repeated items
        last_start, last_end = pos - n, pos
        repeated_group_count += 1
        if repeated_group_count == k:
            k_start, k_end = last_start, last_end

# 2. swap the k-th and the last group
if repeated_group_count > k:
    array[:] = (array[:k_start]
              + array[last_start:last_end]
              + array[k_end:last_start]
              + array[k_start:k_end]
              + array[last_end:])


Это линейный по времени и памяти алгоритм. При желании можно по месту, без дополнительной
памяти замену сделать (к примеру, используя аналог std::rotate()).


Ответ 2

Мне показалось, что со строками будет проще работать, да и вспомнить один трюк из
регулярок захотелось:

def foo(array, k):
    # Представим список как строку
    array_str = ','.join(map(str, array))

    import re
    seq_groups = re.findall(r'((\d)(,\2)+)', array_str)
    if not seq_groups:
        print('Not found groups')

    # Найденные последовательности в списке
    seq_groups = [seq for seq, _, _ in seq_groups]
    print('groups:', seq_groups)

    # Берем все группы после индекса k - 1 и из них выбираем первую
    group_1 = seq_groups[k-1:][0]

    # Берем последнюю группу
    group_2 = seq_groups[-1]

    # Замена одной группы на другую
    array_str = array_str.replace(group_1, "__")
    array_str = array_str.replace(group_2, group_1)
    array_str = array_str.replace("__", group_2)

    # Разбиваем список, приводим все элементы к числу, возвращаем
    # как список
    return list(map(int, array_str.split(',')))


Проверка:

array = [2,2,4,5,5,7,1,6,9,9,9,2]

k = 2
print(foo(array, k))  # [2, 2, 4, 9, 9, 9, 7, 1, 6, 5, 5, 2]

k = 1
print(foo(array, k))  # [9, 9, 9, 4, 5, 5, 7, 1, 6, 2, 2, 2]