Leetcode 150 | День 4: Majority Element
Leetcode 169 предлагает найти элемент большинства в массиве. Элемент большинства встречается более n / 2 раз. Мы предполагаем, что он всегда существует.
Эту задачу можно решить двумя способами.
Подход 1: Метод с использованием Map
Этот метод использует Map для подсчета того, сколько раз встречается каждое число.
- Создайте Map для хранения счетчиков.
- Пройдите циклом по массиву.
- Обновляйте счетчик для каждого числа.
- Пройдите циклом по Map, чтобы найти число, счетчик которого больше n / 2.
Сложность:
- Временная: O(n), так как вы используете два последовательных цикла.
- Пространственная: O(n), так как размер Map растет вместе с количеством уникальных элементов.
Подход 2: Алгоритм голосования Бойера — Мура
Это оптимизированный способ решения задачи с использованием константной памяти.
Представьте, что числа — это противоборствующие команды. Каждый раз, когда число встречается с другим, отличным от него числом, они «аннулируют» друг друга. Поскольку элемент большинства встречается более половины раз, он всегда останется последним.
Как это работает:
- Выберите кандидата и установите счетчик в 0.
- Пройдите циклом по массиву.
- Если счетчик равен 0, назначьте текущее число кандидатом.
- Если текущее число совпадает с кандидатом, увеличьте счетчик на 1.
- Если оно не совпадает, уменьшите счетчик на 1.
Сложность:
- Временная: O(n), так как вы проходите по массиву только один раз.
- Пространственная: O(1), так как вы используете только две переменные.
Почему это важно:
Оба метода имеют временную сложность O(n). Однако второй подход использует гораздо меньше памяти. Ему не требуется Map. Это делает его более эффективным для больших наборов данных.
Источник: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6