Majority Element (Элемент большинства)
Описание: Дан массив nums длины n. Найдите элемент большинства — тот, который встречается более n/2 раз. Гарантируется, что такой элемент существует.
Пример 1:
Вход: nums = [3,2,3]
Выход: 3
Объяснение: Тройка встречается 2 раза из 3
Пример 2:
Вход: nums = [2,2,1,1,1,2,2]
Выход: 2
Объяснение: Двойка встречается 4 раза из 7
Ограничения:
1 <= nums.length <= 5·10⁴
Элемент большинства гарантированно существует
Рекомендуемая временная и пространственная сложность
Стремитесь к решению за O(n) по времени и **O(1) по памяти**.
Подсказка 1
Подсчёт частот хеш-таблицей даёт O(n) памяти. Условие просит O(1).
Подсказка 2
Представьте, что элементы разных видов взаимно уничтожают друг друга. Что останется, если большинства больше половины?
Подсказка 3
Держите кандидата и счётчик. Совпал с кандидатом — увеличиваем, не совпал — уменьшаем. Счётчик обнулился — берём нового кандидата.