Найти максимальное число повторений в O(n) времени и O(1) лишних пробелах

Question

Найдите максимальное число повторений (число, которое встречается чаще всего) за время O(n) и дополнительное пространство O(1).

Я думаю, что я могу использовать фазу подсчета сортировки, которая поддерживает массив счетчиков, тогда это можно сделать за O(N) . Я прав?

Но как справиться с дополнительным пространством. Есть ли другой эффективный алгоритм?

Answer 1

Я не думаю, что это возможно без каких-либо дополнительных знаний о возможных числах в массиве. Для интуиции учтите следующее: для любого постоянного объема памяти, который вы готовы использовать (c = O(1)) есть последовательность, такая что в точке n-1 имеются c+1 Возможности для правильного ответа и только последний номер разрывает связь. В этом случае алгоритм с постоянной памятью c не могу найти ответ за один проход. Это работает аналогично для нескольких (постоянное количество) проходов.

Давайте посмотрим, что мы можем сделать вместо этого.

• Если мы знаем, что есть не более k уникальные числа, мы можем найти ответ в O(n) с O(k) дополнительное пространство, сохраняя массив count (или неупорядоченную карту с постоянной стоимостью поиска, если k числа не должны быть последовательными). Но если мы не можем связать k Кроме как k<n это становится O(n) дополнительное место в худшем случае.
• Если мы отсортируем массив в O(n log(n))мы можем найти ответ в O(n), Таким образом, общая сложность O(n log(n)) с O(1) дополнительное пространство