Обработка групп одинаковых элементов

Серия, или группа, — это подряд идущие элементы массива, равные между собой. На этой странице разберём, как находить начало и конец серии, вычислять её длину, количество серий, максимальную длину и другие свойства. Перед чтением полезно повторить группировку по значению и перебор массива; сама тема входит в страницу группировка элементов.

Что такое серия

Пусть дан массив \(a_1, a_2, \ldots, a_n\). Серия одинаковых элементов — это максимальный непрерывный фрагмент массива, в котором все элементы равны одному значению. Слово «максимальный» означает, что серию нельзя расширить влево или вправо, не нарушив равенство элементов.

Например, в массиве \([4,4,4,2,2,7,7,7,7,1]\) серии имеют вид: \(4\) длины 3, \(2\) длины 2, \(7\) длины 4 и \(1\) длины 1. Одиночный элемент тоже является серией.

Границы и длина серии

Самый удобный способ обработки — идти слева направо. Если текущий элемент равен предыдущему, текущая серия продолжается. Если значения различаются, предыдущая серия закончилась перед текущим элементом, а новая начинается с текущей позиции.

При последовательном просмотре массива часто не хранят обе границы. Достаточно хранить значение текущей серии и её длину. При смене значения длина готовой серии обрабатывается, затем счётчик устанавливается равным 1.

• Начало серии: текущий элемент отличается от предыдущего или это первый элемент.
• Продолжение серии: текущий элемент равен предыдущему.
• Конец серии: следующий элемент отличается или достигнут конец массива.
• После окончания цикла последнюю серию нужно обработать отдельно, если алгоритм реагирует только на смену значения.

Однопроходный алгоритм

Для массива с индексацией от 0 удобно начать с первого элемента. Переменная \(value\) хранит значение серии, а \(length\) — её текущую длину. При встрече нового значения можно обновить ответ: количество серий, максимум длины, сумму или число серий нужного вида.

1a = [4, 4, 4, 2, 2, 7, 7, 7, 7, 1]
2count = 1
3length = 1
4value = a[0]
5max_length = 1
6
7for x in a[1:]:
8    if x == value:
9        length += 1
10    else:
11        count += 1
12        max_length = max(max_length, length)
13        value = x
14        length = 1
15
16max_length = max(max_length, length)

Важен последний оператор обновления максимума. Последняя серия может не сопровождаться сменой значения, поэтому внутри цикла она ещё не была обработана.

Свойства серий

Один проход позволяет вычислять разные характеристики. Число серий увеличивается при каждом переходе \(a_i\ne a_{i-1}\). Максимальная серия обновляется при завершении текущей серии. Можно также посчитать серии заданного значения, серии чётной длины или серии, длина которых больше заданного числа.

Здесь \([P]\) равно 1, если условие \(P\) истинно, и 0 иначе. Формула применима для непустого массива. Если массив может быть пустым, сначала нужно отдельно обработать случай \(n=0\).

Для строк используется тот же подход: символы строки рассматриваются как элементы массива. Например, в строке «AAABCCCAA» серии имеют значения A, B, C, A и длины 3, 1, 3, 2. Подробнее представление строки как последовательности разобрано на странице строка как массив символов.

Разобранный пример

Дан массив \([5,5,2,2,2,8,8,1,1,1,1]\). Требуется найти количество серий, длину максимальной серии и значение, которому она принадлежит. Обработаем массив слева направо, не создавая отдельного списка серий.

Если требуется найти первую максимальную серию, обновляйте ответ только при условии \(length>max\). Если нужна последняя максимальная серия, используйте \(length\ge max\). Это различие часто проверяется в задачах.

Особые случаи и ошибки

• Проверить, что массив непустой перед обращением к первому элементу.
• Понять, считаются ли индексы с 0 или с 1.
• Определить, нужно ли учитывать серии длины 1.
• Обработать последнюю серию после цикла.
• При выводе границ не перепутать индекс нового элемента и индекс последнего элемента старой серии.

Для задач, где элементы сначала нужно переставить, полезно отличать обработку исходных серий от анализа отсортированного массива. О сортировке и одновременном просмотре данных рассказывает страница сортировка и два указателя, а о вычислении самой длинной серии — максимальная серия. Число серий отдельно рассматривается на странице количество серий.