Количество разных элементов в массиве

Question

Можно ли рассчитать количество различных элементов в массиве за линейное время и в постоянном пространстве? Допустим, это массив длинных целых чисел, и вы не можете выделить массив длиной sizeof(long).

P.S. Не домашнее задание, просто любопытно. У меня есть книга, которая подразумевает, что это возможно.

Answer 1

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

Answer 2

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

Answer 3

Вы не можете использовать постоянное пространство. Вы можете использовать O (количество различных элементов) пробел; это то, что делает HashSet.

Answer 4

Это может быть сделано с использованием подхода корзины, если предположить, что существует только постоянное число различных значений. Сделайте флаг для каждого значения (все еще постоянное пространство). Пройдите по списку и отметьте найденные значения. Если вам случится пометить уже помеченное значение, вы нашли дубликат. Вы должны пройти через сегменты для каждого элемента в списке. Но это все еще линейное время.

Answer 5

Если вам гарантировано, что числа в массиве ограничены сверху и снизу, скажем, a и b, то вы можете выделить массив размера b - a и использовать его для отслеживания того, какие числа были замечены.

Т.е., вы должны перемещаться по входному массиву, брать каждое число и отмечать истину в вашем целевом массиве в этом месте. Вы увеличиваете счетчик различных чисел только тогда, когда встречаете число, положение которого в вашем массиве хранения равно false.

Answer 6

Предполагая, что мы можем частично уничтожить ввод, вот алгоритм для n слов из O (log n) битов.

Найти элемент порядка sqrt (n) с помощью линейного выбора времени. Разбейте массив, используя этот элемент в качестве точки разворота (O (n)). Используя грубую силу, подсчитайте количество различных элементов в разделе длины sqrt (n). (Это O (sqrt (n) ^ 2) = O (n).) Теперь используйте сортировку по основанию на остальном, где каждая «цифра» - это log (sqrt (n)) = log (n) / 2 бита, и мы используем первый раздел для хранения количества цифр.

---

Если вы рассматриваете только алгоритмы потоковой передачи (http://en.wikipedia.org/wiki/Streaming_algorithm), то невозможно получить точный ответ с o (n) битами памяти через нижнюю границу сложности связи (http://en.wikipedia.org/wiki/Communication_complexity), но можно приблизить ответ, используя случайность и небольшое пространство (Алон, Матиас и Сегеди).

Answer 7

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