Majority Element

Лёгкая№169подсчёт

Дан массив, в котором одно значение занимает больше половины мест. Нужно найти это значение. Наш пример: [3, 1, 3, 2, 3, 3, 1] — ответ 3, оно встречается 4 раза из 7.

169 Majority ElementРазбор · 1×

Пример: [3, 1, 3, 2, 3, 3, 1]: 7 чисел, значит, ответ встречается больше 3,5 раза. Ниже — словарь: значение и его счётчик.

03112332435361count—
ещё не дошлитекущее числопосчитанобольшинство

Начинаем с пустого словаря: у каждого значения счётчик 0

01/20
сначала · назад · пуск · шаг
Скорость
1function majorityElement(nums):
2 count = empty map // missing keys: 0
3 for each x in nums:
4 count[x] = count[x] + 1
5 if count[x] > len(nums) / 2:
6 return x
состояние
count
{}
x
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Считаем каждое значение по ходу: словарь хранит «значение → сколько раз уже было» и сразу находит счётчик.
  2. Ответ встречается больше n / 2 раз, и тогда никакое другое значение так часто встречаться не может: вместе они не поместились бы в массив. Значит, первый счётчик больше n / 2 — это ответ.
  3. Поэтому можно остановиться сразу: числа после него ответ не изменят.

Сложность

Время O(n): не больше одного прохода. Память O(n): в словаре может оказаться много разных значений. Голосование Бойера — Мура находит ответ с памятью O(1), но это другая идея.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.