Определение большинства в массиве

Условие

Входные данные: массив целых чисел numbers, содержащий n элементов. Необходимо найти majority element – элемент, который встречается более чем n/2 раз. Гарантируется, что такой элемент существует.

Пример 1: Вход: numbers = [3,2,3] Выход: 3

Пример 2: Вход: numbers = [2,2,1,1,1,2,2] Выход: 2

Ограничения: 1 ≤ n ≤ 50000 -10⁹ ≤ numbers[i] ≤ 10⁹ Необходимо реализовать алгоритм со сложностью O(n) по времени и O(1) по дополнительной памяти.

class Solution {
    public int majorityElement(int[] numbers) {
        // Реализация
    }
}

Ответ

Используйте голосование Бойера—Мура: разные значения взаимно погашают голоса, а при нулевом счётчике выбирается новый кандидат. Гарантированное большинство останется кандидатом.

public int majorityElement(int[] numbers) {
    int candidate = 0, count = 0;
    for (int value : numbers) {
        if (count == 0) candidate = value;
        count += value == candidate ? 1 : -1;
    }
    return candidate;
}

Время O(n), дополнительная память O(1). Удаление пары разных значений не уничтожает свойство строгого большинства у искомого числа. Без гарантии существования majority нужен второй проход: подсчитать выбранного кандидата и проверить, что частота строго больше n/2. Пустой массив исходными ограничениями исключён.