Leetcode 150 | День 4: Мажоритарний елемент
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