Найти мажоритарный элемент с помощью хеширования

Опубликовано: 16 Февраля, 2023

Учитывая массив размера N, найдите мажоритарный элемент. Элемент большинства - это элемент, который появляется больше, чем раз в заданном массиве.

Примеры:

Input: [3, 2, 3]
Output: 3

Input: [2, 2, 1, 1, 1, 2, 2]
Output: 2

Проблема была решена с использованием 4 различных методов в предыдущем посте. В этом посте реализовано решение на основе хеширования. Мы считаем вхождения всех элементов. И если количество любого элемента становится больше n/2, мы возвращаем его.

Следовательно, если есть элемент большинства, это будет значение ключа.

Ниже приведена реализация вышеуказанного подхода:

Анализ сложности:

  • Временная сложность: O(n)
  • Вспомогательное пространство: O(n)

РЕКОМЕНДУЕМЫЕ СТАТЬИ