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

Входные данные: массив целых чисел 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) {
        // Реализация
    }
}