Алгоритм большинства с линейным временем?

Может ли кто-нибудь придумать алгоритм линейного времени для определения мажоритарного элемента в списке элементов? Алгоритм должен использовать пробел O (1) .

[Input] 1, 2, 1, 1, 3, 2

[Output] 1

[Примечание редактора] В этом вопросе есть техническая ошибка. Я предпочел оставить его, чтобы не портить формулировку принятого ответа, в котором исправлена ​​ошибка и обсуждается, почему. Проверьте принятый ответ.