Пусть 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]
Ответ
Алгоритм:
найти позиции 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()).
Комментариев нет:
Отправить комментарий