Как вы находите все целые числа в отсортированном массиве размеров N, которые появляются N / K раз?

Question

Я пытаюсь найти решение этой проблемы: Как вы находите все целые числа в отсортированном массиве размеров N, которые появляются N / K раз в Меньше времени , чем o (klognout)?

Я мог бы найти только

Answer 1

Начнем с случая $ k= 2 $ , и предположим, что алгоритм на основе сравнения.

Я утверждаю, что любой алгоритм, который находит даже один элемент, появляющийся $ n / 2 $ Times, должен знать индекс $ i $ такое, что $ a [i + 1]= a [i + n / 2] $ . Действительно, предположим, что это не так, и давайте предположим для простоты, что записи $ a $ являются реальными числами. Скажем, что алгоритм известен следующие значения: $$ [I_1]=CDOTS= A [J_1] Он согласуется со знанием алгоритма, что $ A [I_1-1] и так далее, а с небольшим количеством Усилие мы можем организовать, что нет элемента, появившегося $ N / 2 $ Times.

Рассмотрим сейчас $ n / 2 + 1 $ Массивы следующей формы: есть запуск $ n / 2 $ Многие $ 0 $ s Начать с некоторой позиции $ j \ in \ {1, \ ldots, N / 2 + 1 \} $ , а остальные элементы уникальны. В каждом таком массиве есть уникальный выбор для индекса $ i $ Упомянутый выше. Таким образом, дерево решений, представляющее алгоритм, имеет, по меньшей мере, $ n / 2 + 1 $ листья, и поэтому он должен иметь глубину $ \ Omega (\ log n) $ .

---

В общем случае алгоритм должен знать индекс $ i $ такой, что $ A [I + 1]= A [I + N / K] $ Для каждого элемента, который выводится. Мы можем разбивать массив в $ k / 2 $ Части размера $ 2n / k $ , и рассмотреть $ (N / K + 1) ^ k $ Примеры, как и раньше, где $ R $ Th Появление $ n / k $ Times находится в $ R $ Th. Это дает более низкую границу $ \ Omega (K \ log (n / k)) $ , соответствующий верхней границе почти на все значения $ k $ .

(алгоритмы, вероятно, могут быть вздрогнуты, чтобы дать подходящую верхнюю границу.)