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

Question

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

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

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

Answer 1

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

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

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