У меня есть массив элементов n, в которых только один элемент не повторяется, иначе все остальные числа повторяются > 1 раз. И нет предела в диапазоне чисел в массиве.
Некоторые решения:
O(nlogn), а затем поиск элемента, который не повторяетсяЕсть ли лучшее решение?
Один общий подход заключается в том, чтобы внедрить технику bucketing (из которой хеширование является такой технологией), чтобы распределить элементы в разные "ведра", используя их идентификатор (например, индекс), а затем найти ведро с наименьшим размером (1 в вашем дело). Эта проблема, я считаю, также известна как проблема элементов меньшинства. В вашем наборе будет столько ведер, поскольку в вашем наборе есть уникальные элементы.
Выполнение этого хэширования является проблематичным из-за столкновений и того, как ваш алгоритм может справиться с этим. Некоторые ассоциативные массивные подходы, такие как попытки и расширяемое хэширование, похоже, не применяются, поскольку они лучше подходят для строк.
Одно из применений приведенного выше состоит в структуре Union-Find. Ваши наборы будут ведрами, и вам потребуется вызвать MakeSet() и Find() для каждого элемента в вашем массиве для стоимости $O (\ alpha (n)) $за вызов, где $\ alpha (n) $- чрезвычайно медленно растущая обратная функция Аккермана. Вы можете думать об этом как о постоянной константе.
Вам нужно будет сделать Union, когда элемент уже существует. С некоторыми изменениями, чтобы отслеживать набор с минимальной мощностью, это решение должно работать. Сложность времени этого решения равна $O (n\alpha (n)) $.
Ваша проблема также, по-видимому, слабо связана с проблемой Элемент уникальности.
Попробуйте выполнить многопроходное сканирование, если у вас ограниченное ограничение пространства.
Говорите, что вход имеет 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)
Мне приходят в голову две идеи:
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) - перейдите в свой набор, чтобы найти уникальный элемент), но вам, похоже, не понравилось использование памяти, хотя я не знаю почему. Память дешевая, в эти дни...