Страницы

Поиск по вопросам

среда, 20 февраля 2019 г.

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

Пусть 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()).

Комментариев нет:

Отправить комментарий