¿Encontrar el elemento que no se repite en el conjunto?

Question

Tengo una matriz de n elementos en los que solo un elemento no se repite, de lo contrario todos los demás números se repiten> 1 veces. Y no hay límite en el rango de los números en la matriz.

Algunas soluciones son:

• Haciendo uso de hachís, pero eso daría lugar a la complejidad de tiempo lineal pero muy pobre complejidad espacio
• Ordenar la lista de usando mergesort O(nlogn) y luego encontrar el elemento que no se repite

¿Existe una solución mejor?

Answer 1

Un enfoque general es implementar una técnica de cubicación (de la cual hashing es una técnica) para distribuir los elementos en diferentes "cubos" usando su identidad (digamos índice) y luego encontrar la cubeta con el tamaño más pequeño (1 en Tu caso). Este problema, creo, también se conoce como el problema del elemento minoritario. Habrá tantos cubos como elementos únicos en su conjunto.

Hacer esto por hashing es problemático debido a las colisiones y a cómo su algoritmo podría manejar eso. Ciertos enfoques de matriz asociativa, como los intentos y el hash extensible, no parecen aplicarse, ya que se adaptan mejor a las cadenas.

Una aplicación de las anteriores es para el Union-Find data structure. Sus conjuntos serán los depósitos y tendrá que llamar a MakeSet() y Find() para cada elemento de su matriz por un costo de $ O (\ alpha (n)) $ por llamada, donde $ \ alpha (n) $ es la función Ackermann inversa de crecimiento extremadamente lento. Puedes pensar que es efectivamente una constante.

Deberá hacer Union cuando ya exista un elemento. Con algunos cambios para realizar un seguimiento del conjunto con cardinalidad mínima, esta solución debería funcionar. La complejidad de tiempo de esta solución es $ O (n \ alpha (n)) $.

Tu problema también parece estar ligeramente relacionado con el Element Uniqueness problem.

Answer 2

Pruebe un escaneo de pasos múltiples si tiene una limitación de espacio estricta.

Digamos que la entrada tiene n elementos y solo puede mantener m elementos en la memoria. Si utiliza un enfoque de tablas hash, en el peor de los casos necesita manejar n/2 números únicos, por lo que quiere m> n/2. En caso de que no tenga esa gran m, puede dividir n elementos en k = (max (input) - min (input))/(2m) grupos, y seguir escaneando los n elementos de entrada k veces (en el peor estuche):

1ª ejecución: solo hash-get/put/mark/elementos con valor < min (entrada) + m * 2; porque en el rango (mín. (entrada), mín. (entrada) + m * 2) hay como máximo m elementos únicos y usted puede manejar eso. Si tiene suerte, ya encontrará la única, de lo contrario, continúe.

segunda carrera: sólo operan en elementos con valor en el rango de (min (de entrada) + m * 2, min (de entrada) + m * 4), y así sucesivamente, etc.

De esta manera, que pongan en peligro la complejidad del tiempo a un O (kn), pero se obtiene una complejidad espacial con destino de O (m)

Answer 3

dos ideas vienen a la mente:

• un smoothsort puede ser una alternativa mejor que el mergesort citado para sus necesidades dado que es O (1) en uso de memoria, O (nlogn) en el peor de los casos e como el tipo de fusión pero O (n) en el mejor de los casos;

• Partiendo de la idea (inversa) de la splay tree, se puede hacer un tipo de árbol que empujar las hojas hacia la parte inferior una vez que se utilizan (en lugar de hacia arriba como en el árbol biselado). Esto aún le daría una implantación O (nlogn) del tipo, pero la ventaja sería el paso O (1) de encontrar el elemento único, sería la raíz. El algoritmo de clasificación es la suma de O (nlogn) + O (n) y este algoritmo sería O (nlogn) + O (1)

De lo contrario, como ha afirmado, utilizando una solución basada almohadilla (como conjunto implementado con hash) daría como resultado un algoritmo O (n) (O (n) para insertar y agregar una referencia de conteo a él y O (n) para recorrer el conjunto para encontrar el elemento único) pero parecía que no le gustaba la memoria uso, aunque no sé por qué. La memoria es barata, en estos días ...