Мажоритарный элемент

Постановка задачи

nums = [3, 2, 3]

3

nums = [2, 2, 1, 1, 1, 2, 2]

2

Решение

На интервью задача на поиск мажоритарного элемента - это классический фильтр на знание алгоритмической оптимизации. Ее дают, чтобы проверить, знает ли кандидат как перейти от базового решения "в лоб" к оптимизированному по памяти решению.

Подвох: часто интервьюеры просят решить задачу строго за O(1) по памяти и за O(n) время. Это сразу отсекает использование таблицы частот элементов и намекает на алгоритм голосования.

Самый наивный способ - для каждого элемента в массиве заново подсчитывать, сколько раз он встречается во всем остальном массиве:

• Берем первый элемент. Проходим циклом по всему массиву и считаем вхождения.
• Если счетчик больше ⌊n / 2⌋, возвращаем этот элемент.
• Если нет - переходим ко второму элементу и повторяем процесс.

Хотя такое решение действительно использует O(1) памяти, оно имеет O(n²) временную сложность и не подойдет.

Решение получше - это использовать таблицу частот элементов (в виде хеш-таблицы) и за один проход подсчитывать количество вхождений каждого числа, обновляя частоту в таблице:

• Создаем хеш-таблицу, где ключ - число, а значение - сколько раз оно встретилось.
• Проходим по массиву и заполняем таблицу.
• Если счетчик какого-то числа превысил ⌊n / 2⌋, возвращаем его.

Такое решение намного лучше по времени: O(n), но теперь нам нужно также и O(n) памяти для хранения частот элементов.

Давайте попробуем оптимизировать решение с таблицей частот. Рассмотрим последний элемент в массиве и отрезок массива до последнего элемента.

Пусть у нас уже есть кандидат на мажоритарный элемент из этого отрезка массива.

Вопрос: когда мы видим последний элемент, что происходит с кандидатом?

Тут два варианта. Либо последний элемент совпадает с кандидатом, либо нет. Если совпадает, то он усиливает ("подтверждает") кандидата.

Если же отличается, то кандидат либо остается мажоритарным, либо последний элемент "побеждает" и сам становится мажоритарным (здесь мы исходим из того, что мажоритарный элемент всегда существует в массиве).

Чтобы кандидат проиграл, число его вхождений в отрезок должно быть меньше или равно числу вхождений в отрезок последнего элемента, тогда последний элемент перевесит и сам станет мажоритарным.

Таким образом, нам нужно что-то знать о кандидате, чтобы принять решение о том, что он "проиграл". Что-то вроде: "насколько этот кандидат силен", "какой у него вес", "сколько за него голосов" или "сколько его экземпляров выжило".

Это ключевая идея: поддерживать вес кандидата (количество голосов за него).

Когда мы идем по массиву, мы первым делом смотрим на вес кандидата. Если он равен нулю, то текущий элемент становится нашим новым кандидатом. Если же вес больше нуля, мы сравниваем элемент с кандидатом: при совпадении мы "усиливаем" его, увеличивая вес, а при отличии - вес уменьшается (элемент поглощает экземпляр кандидата).

Это и есть тот самый классический алгоритм голосования Бойера-Мура (Boyer-Moore Voting Algorithm). Его часто называют просто "алгоритмом большинства". Его суть

• это процесс "взаимного уничтожения" разных элементов, где выживает только тот, чье количество изначально превышало половину.

Основные шаги:

1. Инициализируем две переменные: candidate (любое число) и count = 0.
2. Идем циклом по массиву:
   • Если count равен 0, назначаем текущий элемент новым candidate.
   • Если текущий элемент равен candidate, прибавляем 1 к count.
   • В противном случае уменьшаем count.
3. После завершения цикла candidate и будет искомым мажоритарным элементом.

Пример 1:

Как это работает на примере [3, 2, 3].

1. Инициализация: candidate = 0, count = 0.

2. Число 3: count ноль, назначаем кандидата:
   • candidate = 3, count = 1.

3. Число 2: не равно candidate, уменьшаем вес кандидата:
   • count = 0.

4. Число 3: count ноль, назначаем кандидата:
   • candidate = 3.

В итоге получили результат: 3.

В этой задаче ограничение "мажоритарный элемент всегда существует" - это важная подсказка, которая упрощает решение. Мы можем сразу вернуть найденного кандидата. С точки зрения интервьюера, это ограничение часто вводится намеренно, чтобы сфокусировать ваше внимание на поиске способа оптимизации памяти.

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

Оценка сложности

Временная сложность

Временная сложность O(n), так как мы проходим по массиву ровно один раз с помощью одного цикла.

Пространственная сложность

Для решения нам требуется только несколько переменных типа int, то есть это константная сложность: O(1).

Это решение является оптимальным.

Код решения

Теперь можем написать код решения.

func majorityElement(nums []int) int {
    candidate := 0
    count := 0
 
    for i := 0; i < len(nums); i++ {
        // голоса обнулились, выбираем нового кандидата
        if count == 0 {
            candidate = nums[i]
        }
 
        // текущее число совпадает с кандидатом, прибавляем голос
        // иначе - отнимаем
        if nums[i] == candidate {
            count++
        } else {
            count--
        }
    }
 
    return candidate
}

Итоги

Задача о мажоритарном элементе - это отличный пример того, как знание специфического алгоритма позволяет перейти от "просто рабочего" кода к максимально эффективному.

1. Главное свойство: если элемент встречается более чем в половине случаев, он всегда сможет "пережить" встречу со всеми остальными элементами вместе взятыми.
2. Эффективное решение: алгоритм голосования Бойера-Мура, сложность по времени O(n), сложность по памяти O(1).
3. Критическая деталь: всегда уточняйте, гарантировано ли наличие мажоритарного элемента. Если нет - обязателен второй проход для проверки финального кандидата.
4. Где пригодится: принципы этого алгоритма лежат в основе систем обработки потоковых данных, защиты от DDoS-атак и систем распределенного консенсуса.