Найдите, существует ли элемент, повторяющийся n/k времена

Я не знаю, есть ли ограничения на то, какие дополнительные структуры данных вы можете использовать.

Как насчет создания хэшмапа с отображением 'elements' <--> count. Вставка - O(log N). Поиск - O(1). Для каждого элемента ищем в хеш-таблице, вставляем, если не существует, с количеством 1. Если существует, проверяем, что count < (n/k). Это останется O(n).

EDIT:

Я забыл про ограничение постоянной памяти. Это предварительное выделение записей хэш-карты с N элементами разрешено?

Я не уверен на 100%, но похоже, что вы хотите решить проблему Бритни Спирс - найти элемент, который составляет определенную долю выборки, используя постоянную память.

Вот постановка проблемы на английском языке с наброском решения:

… из статьи Эрика 2002 года. Д. Демейн из Массачусетского технологического института и Алехандро Лопес-Ортис и Йен Манро из Университет Ватерлоо в Канаде. Демейн и его коллеги расширил алгоритм, чтобы покрыть более общая проблема: данный поток длины n, определите набор размера m что включает в себя все элементы происходит с большей частотой чем n / (m +1). (В случае m = 1, это сводится к проблеме большинства.) Расширенный алгоритм требует m регистры для элементов-кандидатов а также счетчики м. Базовый схема работы аналогична алгоритм большинства. Когда элемент потока соответствует одному из кандидаты, соответствующий счетчик увеличивается; когда нет совпадения любому кандидату, все счетчики уменьшаются; если счетчик на 0, связанный кандидат заменен новым элементом из потока.

Простой алгоритм O (n) будет хранить хешированную карту от найденного числа до числа найденных экземпляров. Использование хешированной карты важно для поддержания O (n). Последний проход по карте откроет ответы. Этот проход также является O (n), поскольку в худшем случае каждый элемент появляется только один раз, и, следовательно, карта имеет тот же размер, что и исходный массив.