Определение конкретного числа в времени и пространстве (наихудший случай)

$\newcommand\ldotd{\mathinner{..}}$ Учитывая, что $A[1\ldotd n]$ являются целыми числами, такими, что $0\le A[k]\le m$ для всех $1\le k\le n$ , и вхождением каждого число, кроме определенного числа в $A[1\ldotd n]$ является нечетным числом. Попробуйте найти число, вхождение которого является четным числом.

Существует алгоритм $\Theta(n\log n)$ : мы сортируем $A[1\ldotd n]$ на $B[1\ldotd n]$ и разбиваем $B[1\ldotd n]$ на множество частей, значения элементов которых являются то же самое, поэтому мы можем посчитать вхождение каждого элемента.

Я хочу найти алгоритм $O(n)$ -время-и- $O(n)$ -пространства в худшем случае .

Предположим, что $m=\Omega(n^{1+\epsilon})$ и $\epsilon>0$ , поэтому радикальная сортировка недопустима. $\DeclareMathOperator{\xor}{xor}$ Двоичные побитовые операции допустимы, например, $A[1]\xor A[2]$ .

Вот идея простого алгоритма; просто посчитай все вхождения!

1. Найти . - время$m = \max A$$\Theta(n)$
2. «Выделить» массив . - время ¹$C[0..m]$$O(1)$
3. Итерируйте по и увеличивайте на единицу всякий раз, когда вы найдете . Если было , добавить до линейного списка . - время$A$$C[x]$$A[\_]=x$$C[x]$$0$$x$$L$$\Theta(n)$
4. Переберите и найдите элемент с . - время .$L$$x_e$$C[x_e]$$O(n)$
5. Вернуть .$x_e$

В общем, это дает вам алгоритм линейного времени, который может использовать (в смысле выделения) много памяти. Обратите внимание, что возможность произвольного доступа к в постоянное время независимо от имеет решающее значение.$C$$m$

При таком подходе дополнительная оценка является более сложной; Я не знаю какой-либо словарной структуры данных, которая предлагает поиск времени. Вы можете использовать хеш-таблицы, для которых здесь есть реализации с ожидаемым временем поиска ( размером таблицы, числом хранимых элементов), так что вы можете получить сколь угодно хороший результат с линейным пространством - в ожидании. Если все значения в соответствуют одному и тому же хеш-значению, вы облажались.$O(n)$$O(1)$$O(1 + k/n)$ $n$$k$$A$

1. В оперативной памяти это сделано неявно; все, что нам нужно, это начальная позиция и, возможно, конечная позиция.

Почти тривиальное решение - использующее, однако, пространство - это использование хэш-карты. Напомним, что хэш-карта имеет амортизированную среду выполнения для добавления и поиска элементов.$\Theta(n)$$\mathcal{O}(1)$

Следовательно, мы можем использовать следующий алгоритм:

1. Выделяют хэш - карту . Итерация над . Для каждого элемента увеличьте количество видимых случаев, т.е. .$H$$A$$i \in A$$H(i)++$

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

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