Почему это работает
- Считаем каждое значение по ходу: словарь хранит «значение → сколько раз уже было» и сразу находит счётчик.
- Ответ встречается больше n / 2 раз, и тогда никакое другое значение так часто встречаться не может: вместе они не поместились бы в массив. Значит, первый счётчик больше n / 2 — это ответ.
- Поэтому можно остановиться сразу: числа после него ответ не изменят.
Сложность
Время O(n): не больше одного прохода. Память O(n): в словаре может оказаться много разных значений. Голосование Бойера — Мура находит ответ с памятью O(1), но это другая идея.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗