Найти один неповторяющийся элемент в массиве?

Ответ 1

Один общий подход заключается в том, чтобы внедрить технику bucketing (из которой хеширование является такой технологией), чтобы распределить элементы в разные "ведра", используя их идентификатор (например, индекс), а затем найти ведро с наименьшим размером (1 в вашем дело). Эта проблема, я считаю, также известна как проблема элементов меньшинства. В вашем наборе будет столько ведер, поскольку в вашем наборе есть уникальные элементы.

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

Одно из применений приведенного выше состоит в структуре Union-Find. Ваши наборы будут ведрами, и вам потребуется вызвать MakeSet() и Find() для каждого элемента в вашем массиве для стоимости $O (\ alpha (n)) $за вызов, где $\ alpha (n) $- чрезвычайно медленно растущая обратная функция Аккермана. Вы можете думать об этом как о постоянной константе.

Вам нужно будет сделать Union, когда элемент уже существует. С некоторыми изменениями, чтобы отслеживать набор с минимальной мощностью, это решение должно работать. Сложность времени этого решения равна $O (n\alpha (n)) $.

Ваша проблема также, по-видимому, слабо связана с проблемой Элемент уникальности.

Ответ 2

Попробуйте выполнить многопроходное сканирование, если у вас ограниченное ограничение пространства.

Говорите, что вход имеет n элементов, и вы можете удерживать только m элементов в своей памяти. Если вы используете подход хеш-таблицы, в худшем случае вам нужно обрабатывать n/2 уникальных номера, поэтому вы хотите m > n/2. Если у вас нет этого большого m, вы можете разделить n элементов на k = (max (input) -min (input))/(2m) группы и продолжить поиск n элементов ввода k раз (в худшем случай):

1-й прогон: вы только hash-get/put/mark/любые элементы со значением < мин (вход) + т * 2; потому что в диапазоне (min (input), min (input) + m * 2) существует не более m уникальных элементов, и вы можете справиться с этим. Если вам повезет, вы уже нашли уникальный, в противном случае продолжайте.

2-й прогон: работают только с элементами со значением в диапазоне (мин (вход) + м * 2, мин (вход) + м * 4) и так далее, и т.д.

Таким образом, вы ставите под угрозу сложность времени для O (kn), но вы получаете оценку сложности пространства O (m)

Ответ 3

Мне приходят в голову две идеи:

• A smoothsort может быть лучшей альтернативой, чем цитированный mergesort для ваших потребностей, учитывая его использование O (1) в памяти, O (nlogn) в худшем случае как сортировка слияния, но O (n) в лучшем случае;

• Основываясь на (обратном) представлении splay tree, вы можете создать тип дерева, который толкайте листья вниз, как только они будут использоваться (вместо того, чтобы подниматься вверх, как в дереве). Это все равно даст вам O (nlogn) имплантацию такого рода, но преимуществом будет O (1) шаг поиска уникального элемента, это будет корень. Алгоритм сортировки представляет собой сумму O (nlogn) + O (n), и этот алгоритм будет O (nlogn) + O (1)

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