Determinar el número particular en

$\newcommand\ldotd{\mathinner{..}}$ Dado que $A[1\ldotd n]$ son enteros tales que $0\le A[k]\le m$ para todos $1\le k\le n$ , y la aparición de cada uno número excepto un número particular en $A[1\ldotd n]$ es un número impar. Intenta encontrar el número cuya aparición es un número par.

Hay un algoritmo $\Theta(n\log n)$ : clasificamos $A[1\ldotd n]$ en $B[1\ldotd n]$ , y $B[1\ldotd n]$ en muchas piezas, cuyo valor de elementos es el igual, por lo tanto, podemos contar la ocurrencia de cada elemento.

Quiero encontrar un algoritmo para el peor de los casos: $O(n)$ -hora-y- $O(n)$ -espacio.

Suponiendo que $m=\Omega(n^{1+\epsilon})$ y $\epsilon>0$ , por lo tanto, la clasificación de radix no es aceptable. $\DeclareMathOperator{\xor}{xor}$ Las operaciones binarias bit a bit son aceptables, por ejemplo, $A[1]\xor A[2]$ .

algorithms search-algorithms Yai0Phah
fuente

La respuesta de Aryabhata a continuación muestra que el caso general no es bueno, pero ¿quizás tenga más restricciones disponibles? Una restricción simple (pero grande) sería exigir que todas las entradas de la matriz tengan un tamaño . Esto daría un algoritmo lineal bastante trivial.

O (n)

$O(n)$

Luke Mathieson

@LukeMathieson: eliminé esa respuesta, ya que aún no estoy convencido de que el documento que cité funcionará sin ninguna modificación, y además, OP parece estar interesado solo en el modelo de RAM de costo uniforme.

Aryabhata

@Aryabhata: jeje, bueno, ¡la respuesta no está ahí entonces! Por interesante y quizás útil para Frank, ¿cuál crees que fue el problema de adaptar el resultado en el documento? Una ojeada rápida sugirió que se aplicara, pero obviamente no lo leí.

Luke Mathieson

@LukeMathieson: El hecho de que los otros elementos deben aparecer un número impar de veces en el problema actual. Desde entonces, también leí la prueba ...

Aryabhata

Sería interesante si está interesado en resultados teóricos o en soluciones prácticas. Desde el punto de vista de la teoría, mi primera respuesta rápida es, que usted puede ordenar una lista de números enteros más rápido que . Hay un algoritmo determinista de Han que se ejecuta en tiempo . Para algoritmos aleatorios, se conocen resultados aún mejores, por ejemplo, Han y Thorup han encontrado un algoritmo de tiempo esperado . Sin embargo, creo que su problema no debería requerir clasificación.

O (n \log n)

$O(n\log n)$

O (\log \log n)

$O(\log\log n)$

O (n \sqrt{\log \log n})

$O(n \sqrt{\log\log n})$

A.Schulz

Respuestas:

Aquí hay una idea para un algoritmo simple; ¡solo cuenta todas las ocurrencias!

Encuentra . - tiempo $m = \max A$ $\Theta(n)$
"Asignar" la matriz . - tiempo ¹ $C[0..m]$ $O(1)$
Itere sobre y aumente en uno cada vez que encuentre . Si era , Añadir a una lista lineal . - tiempo $A$ $C[x]$ $A[\_]=x$ $C[x]$ $0$ $x$ $L$ $\Theta(n)$
Iterar sobre y encontrar el elemento con par. - tiempo . $L$ $x_e$ $C[x_e]$ $O(n)$
Devuelve . $x_e$

Con todo, esto le proporciona un algoritmo de tiempo lineal que puede usar (en el sentido de asignar) mucha memoria. Tenga en cuenta que poder acceder aleatoriamente a en tiempo constante independientemente de es crucial aquí. $C$ $m$

Un adicional en el espacio es más difícil con este enfoque; No conozco ninguna estructura de datos del diccionario que ofrezca búsqueda de tiempo . Puede usar tablas hash para las que aquí hay implementaciones con tiempo de búsqueda esperado ( el tamaño de la tabla, el número de elementos almacenados) para que pueda obtener arbitrariamente bien con espacio lineal, en expectativa. Si todos los valores en asignan al mismo valor hash, estás jodido. $O(n)$ $O(1)$ $O(1 + k/n)$ $n$ $k$ $A$

En una RAM, esto se hace implícitamente; todo lo que necesitamos es la posición inicial y quizás la posición final.

Rafael
fuente

Una solución casi trivial, que utiliza sin embargo el espacio , es utilizar un mapa hash. Recuerde que un mapa hash ha amortizado el tiempo de ejecución para agregar y buscar elementos. $\Theta(n)$ $\mathcal{O}(1)$

Por lo tanto, podemos usar el siguiente algoritmo:

Asignar un mapa hash . Iterar sobre . Para cada elemento , aumente el número de ocurrencias observadas, es decir, . $H$ $A$ $i \in A$ $H(i)++$
Itere a través del conjunto de claves del mapa hash y compruebe cuál de las claves tiene un recuento par de ocurrencias.

Ahora, este es un algoritmo simple que realmente no usa ningún truco grande, pero a veces incluso esto es suficiente. De lo contrario, es posible que desee especificar qué restricciones de espacio impone.

HdM
fuente

Todavía me gustaría saber si hay un algoritmo de tiempo no aleatorio que usa espacio polinomial. En particular, ¿hay alguna evidencia teórica de que encontrar el único elemento que es par es más difícil que encontrar el único elemento impar?

O (n)

$O(n)$

A.Schulz

@ A.Schulz Creo que es el algoritmo de tiempo esperado al usar la tabla hash. Recuerdo que alguien me dijo un algoritmo (o para algún caso especial, por ejemplo, impar = 1 e incluso = 2) tal vez con stack, pero no puedo recordarlo.

O (n)

$O(n)$

O (n)

$O(n)$

Yai0Phah

No todas las implementaciones de tablas hash tienen esta propiedad; generalmente, la búsqueda no es , ni siquiera amortizada (afaik). De hecho, una discusión previa no ha dado lugar a ninguna implementación que tenga una búsqueda constante en el tiempo. ¿Puedes ser mas específico?

O (1)

$O(1)$

Raphael