Задача с собеседования в Zenefits

Задача с собеседования в Zenefits Дан массив nums размером n, верните элемент большинства (гарантируется, что он всегда есть в массиве). Элемент большинства (или мажоритарный) - это преобладающий элемент последовательности, который в данном случае должен встречаться более, чем n / 2 раз. Решите задачу за линейное время и с O(1) по памяти. Пример 1: Input: nums = [3,2,3] Output: 3 Пример 2: Input: nums = [2,2,1,1,1,2,2] Output: 2 НАШ ЧАТ АЛГОРИТМИСТОВ Решение Без дополнительного условия на асимптотику задачу можно было бы решить с использованием хэш-таблицы, где ключ - элемент массива, а значение - кол-во его вхождений в массив. Сложность при этом: O(n) - по времени и O(n) - по памяти. С учётом условия улучшения пространственной сложности до O(1), оптимальным и стандартным будет использование алгоритма Бойера-Мура: Создаём две переменные: result (содержит элемент, претендующий на то, чтобы оказаться мажоритарным) и count (счётчик "приоритета" элемента-кандидата на преобладание в последовательности). В начале цикла кандидатом окажется элемент, идущий первым в массиве, увеличиваем счётчик его "приоритета" на 1. Далее мы сравниваем каждый последующий элемент с текущим значением result, если они равны - увеличиваем счётчик, если нет - уменьшаем. Если в какой-то момент счётчик приоритета становится равным 0, выбираем нового кандидата и записываем в result. Так проходим по всем эл-там массива и в конце выводим result с последним вписанным в него значением. Таким образом, суть алгоритма в симуляции попарного "обнуления" противоположных элементов путём уменьшения счётчика count. Так как преобладающий эл-т составляет больше половины всей последовательности, в процессе для него не останется противоположного элемента для попарного "удаления". Наличие мажоритарного эл-та гарантируется условием задачи, поэтому нам не нужна дополнительная проверка. Сложность O(n) - по времени O(1) - по памяти Код class Solution: def majorityElement(self, nums: List[int]) -> int: result, count = 0, 0 for i in nums: if count == 0: result = i count += 1 elif i == result: count += 1 else: count -= 1 return result @algoses