Найти мажоритарный элемент с помощью хеширования
Опубликовано: 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)