169. Элемент большинства

Условие

169. Элемент большинства

Получив массив nums размером n, верните элемент, занимающий большинство.

Элемент большинства — это элемент, который встречается в массиве более определенного [n / 2] количества раз. Можно предположить, что элемент большинства всегда присутствует в массиве.

Пример 1: Входные данные: nums = [3,2,3] Выходные данные: 3

Пример 2: Входные данные: nums = [2,2,1,1,1,2,2] Выходные данные: 2

Ограничения:

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9
• Входные данные генерируются таким образом, чтобы в массиве присутствовал элемент, занимающий доминирующее положение.

Ответ

Алгоритм голосования Бойера — Мура находит элемент большинства за O(n) времени и O(1) дополнительной памяти при гарантии его существования.

def majority_element(nums):
    candidate = None
    count = 0
    for value in nums:
        if count == 0:
            candidate = value
        count += 1 if value == candidate else -1
    return candidate

Разные элементы взаимно «сокращаются», а значение, встречающееся чаще n/2, остаётся кандидатом. Если гарантии большинства нет, вторым проходом проверьте число вхождений. По условию массив непустой.