Самый распространенный элемент в массиве / Нахождение относительного большинства детерминистически за O (n )времени и O (1 )пространства?

Так, например, ответ для массива:

1, 11, 3, 95, 23, 8, 1

будет 1, так как все остальные элементы встречаются только один раз, а 1 встречается дважды.

Многие вопросы, подобные этому вопросу, которые я видел в stackoverflow, просят найти абсолютное большинство (, ответ встречается как минимум n/2 в массиве длины n ), или ответить на вопрос, используя сортировку или хэш-таблица.Первое — это не то, о чем я спрашиваю, а второе либо слишком медленно (O (n log n )для сортировки ), либо использует слишком много памяти (O (n )для хеш-таблицы ).

Существует ли такой алгоритм? Если нет, то есть ли доказательства, почему это невозможно? Включение источника было бы неплохо.