Un elemento que difiere en dos matrices. ¿Cómo encontrarlo de manera eficiente?

Me estoy preparando para una entrevista de codificación y realmente no puedo encontrar la forma más eficiente de resolver este problema.

Digamos que tenemos dos matrices que consisten en números que no están ordenados. La matriz 2 contiene un número que la matriz 1 no tiene. Ambas matrices tienen números ubicados al azar, no necesariamente en el mismo orden o en los mismos índices. Por ejemplo:

Matriz 1 [78,11, 143, 84, 77, 1, 26, 35 .... n]

Matriz 2 [11,84, 35, 25, 77, 78, 26, 143 ... 21 ... n + 1]

¿Cuál es el algoritmo más rápido para encontrar el número que difiere? ¿Cuál es su tiempo de ejecución? En este ejemplo, el número que estaríamos buscando es 21.

Mi idea era ejecutar a través de la matriz 1 y eliminar ese valor de la matriz 2. Iterar hasta que haya terminado. Esto debería ser alrededor del tiempo de ejecución , ¿verdad?$O(n \log n)$

Veo cuatro formas principales de resolver este problema, con diferentes tiempos de ejecución:

• $O(n^2)$Solución : esta sería la solución que propones. Tenga en cuenta que, dado que las matrices no están ordenadas, la eliminación lleva tiempo lineal. Realizas eliminaciones; por lo tanto, este algoritmo lleva tiempo cuadrático.$n$

• $O(n \: log \: n)$Solución : ordenar las matrices de antemano; luego, realice una búsqueda lineal para identificar el elemento distinto. En esta solución, el tiempo de ejecución está dominado por la operación de clasificación, de ahí el límite superior .$O(n \: log \: n)$

Cuando identifica una solución a un problema, siempre debe preguntarse: ¿puedo hacerlo mejor? En este caso, puede hacerlo, haciendo un uso inteligente de las estructuras de datos. Tenga en cuenta que todo lo que necesita hacer es iterar una matriz y realizar búsquedas repetidas en la otra matriz. ¿Qué estructura de datos le permite realizar búsquedas en tiempo constante (esperado)? Has acertado: una tabla hash .

• $O(n)$Solución (esperada): itere la primera matriz y almacene los elementos en una tabla hash; luego, realice una exploración lineal en la segunda matriz, buscando cada elemento en la tabla hash. Devuelve el elemento que no se encuentra en la tabla hash. Esta solución de tiempo lineal funciona para cualquier tipo de elemento que pueda pasar a una función hash (por ejemplo, funcionaría de manera similar para matrices de cadenas).

Si desea garantías de límite superior y las matrices están estrictamente compuestas de enteros, la mejor solución es, probablemente, la sugerida por Tobi Alafin (aunque esta solución no le dará el índice del elemento que difiere en la segunda matriz) :

• $O(n)$Solución (garantizada): resume los elementos de la primera matriz. Luego, resume los elementos de la segunda matriz. Finalmente, realiza la resta. Tenga en cuenta que esta solución se puede generalizar a cualquier tipo de datos cuyos valores se puedan representar como cadenas de bits de longitud fija, gracias al operador XOR bit a bit . Esto se explica a fondo en la respuesta de Ilmari Karonen .

Finalmente, otra posibilidad (bajo la misma suposición de matrices de enteros) sería usar un algoritmo de ordenación de tiempo lineal como la ordenación de conteo. Esto reduciría el tiempo de ejecución de la solución basada en la clasificación de a O ( n ) .$O(n \: log \: n)$$O(n)$

El diferencia de sumas solución propuesta por Tobi y Mario de hecho, puede ser generalizado a cualquier otro tipo de datos para los que podemos definir un (constante de tiempo) operación binaria ⊕ que es:$\Theta(n)$$\oplus$

• total de , tal que para cualquier valor de y b , un ⊕ b se define y del mismo tipo (o al menos de algunos supertipo apropiada de la misma, para que el operador ⊕ todavía se define);$a$$b$$a \oplus b$$\oplus$
• asociativo , tal que ;$a \oplus (b \oplus c) = (a \oplus b) \oplus c$
• conmutativo , de modo que ; y$a \oplus b = b \oplus a$
• cancelativo , de modo que existe un operador inverso que satisface ( a ⊕ b ) ⊖ b = a . Técnicamente, esta operación inversa ni siquiera tiene que ser necesariamente de tiempo constante, siempre y cuando "restar" dos sumas de n elementos cada una no tome más de O ( n ) tiempo.$\ominus$$(a \oplus b) \ominus b = a$$n$${\rm O}(n)$

(Si el tipo solo puede tomar un número finito de valores distintos, estas propiedades son suficientes para convertirlo en un grupo abeliano ; incluso si no, al menos será un semigrupo conmutativo cancelativo ).

Usando tal operación , podemos definir la "suma" de una matriz a = ( a 1 , a 2 , ... , a n ) como ( $\oplus$$a = (a_1, a_2, \dots, a_n)$ Dada otra matriz b = ( b 1 , b 2 , … , b n , b n + 1 ) que contiene todos los elementos de a más un elemento extra x , tenemos (

$\oplus$$\ominus$$\oplus$$\ominus$

En términos más generales, incluso podemos aplicar el método XOR bit a bit a cadenas de longitud variable, rellenándolas hasta la misma longitud que sea necesaria, siempre que tengamos alguna forma de eliminar el relleno de forma reversible al final.

En algunos casos, esto es trivial. Por ejemplo, las cadenas de bytes terminadas en nulo estilo C codifican implícitamente su propia longitud, por lo que aplicar este método para ellas es trivial: cuando XORing dos cadenas, rellene la más corta con bytes nulos para hacer que su longitud coincida, y recorte cualquier nulo final adicional de el resultado final. Sin embargo, tenga en cuenta que las cadenas de suma XOR intermedias pueden contener bytes nulos, por lo que deberá almacenar su longitud explícitamente (pero solo necesitará uno o dos como máximo).

$1$$0$$0$$1$$2^{32}$bytes de longitud, podríamos codificar la longitud de cada cadena como un entero de 32 bits y anteponerla a la cadena. O incluso podríamos codificar longitudes de cadena arbitrarias utilizando algún código de prefijo y anteponerlas a las cadenas. También existen otras posibles codificaciones.

$\Theta(n)$

La única parte potencialmente complicada es que, para que la cancelación funcione, necesitamos elegir una representación de cadena de bits canónica única para cada valor, lo que podría ser difícil (de hecho, potencialmente incluso computacionalmente indecidible) si se pueden proporcionar los valores de entrada en las dos matrices. en diferentes representaciones equivalentes. Sin embargo, esta no es una debilidad específica de este método; cualquier otro método para resolver este problema también puede fallar si se permite que la entrada contenga valores cuya equivalencia es indecidible.

Publicaría esto como un comentario sobre la respuesta de Tobi, pero aún no tengo la reputación.

Como alternativa al cálculo de la suma de cada lista (especialmente si son listas grandes o contienen números muy grandes que pueden desbordar su tipo de datos cuando se suman), puede usar xor en su lugar.

Simplemente calcule la suma xor (es decir, x [0] ^ x [1] ^ x [2] ... x [n]) de cada lista y luego xor esos dos valores. Esto le dará el valor del elemento extraño (pero no el índice).

Esto sigue siendo O (n) y evita cualquier problema de desbordamiento.

Elemento = Suma (Array2) - Suma (Array1)

Yo sinceramente dudo que esto es el algoritmo más óptimo. Pero es otra forma de resolver el problema, y ​​es la forma más simple de resolverlo. Espero eso ayude.

Si el número de elementos agregados es más de uno, esto no funcionará.

Mi respuesta tiene la misma complejidad de tiempo de ejecución para el mejor, el peor y el caso promedio,

EDITAR
Después de pensar un poco, creo que mi respuesta es tu solución.

$n$$n-1$$1 = n-1$$2 = n+1 -1=n$

$2n-1$$2 -$$1 = 1$

$2n - 1 + 1 = 2n$

EDITAR:
debido a algunos problemas con los tipos de datos, una suma XOR según lo sugerido por reffu será más adecuada.

Suponiendo que la matriz 2 se creó tomando la matriz 1 e insertando un elemento en una posición aleatoria, o la matriz 1 se creó tomando la matriz 2 y eliminando un elemento aleatorio.

Si se garantiza que todos los elementos de la matriz sean distintos, el tiempo es O (ln n). Compara los elementos en la ubicación n / 2. Si son iguales, el elemento adicional es de n / 2 + 1 hasta el final de la matriz, de lo contrario es de 0 a n / 2. Y así.

Si no se garantiza que los elementos de la matriz sean distintos: podría tener n veces el número 1 en la matriz 1 y el número 2 insertado en cualquier lugar de la matriz 2. En ese caso, no puede saber dónde está el número 2 sin mirar en absoluto elementos de la matriz Por lo tanto, O (n).

PD. Como los requisitos cambiaron, verifique en su biblioteca lo que está disponible. En macOS / iOS, crea un NSCountedSet, agrega todos los números de la matriz 2, elimina todos los números de la matriz 1, y lo que queda es todo lo que está en la matriz 2 pero no en la matriz 1, sin depender de la afirmación de que hay uno adicional ít.

var más corto, más largo;

Convierta el más corto en un mapa para una referencia rápida y el ciclo durante el más largo hasta que el valor actual no esté en el mapa.

Algo como esto en javascript:

if (arr1.length> arr2.length) {shortest = arr2; más largo = arr1; } else {más corto = arr1; más largo = arr2; }

var map = shortest.reduce (function (obj, value) {obj [value] = true; return obj;}, {});

diferencia var = longest.find (function (value) {return !!! map [value];});

Solución O (N) en complejidad temporal O (1) en términos de complejidad espacial

Planteamiento del problema: suponiendo que la matriz2 contiene todos los elementos de la matriz1 más otro elemento no presente en la matriz1.

La solución es: Usamos xor para encontrar el elemento que no está presente en la matriz1, por lo que los pasos son: 1. Comience desde la matriz1 y haga xor de todos los elementos y almacénelos en una variable. 2. Tome el array2 y haga el xor de todos los elementos con la variable que almacena el xor de array1. 3. Después de hacer la operación, nuestra variable contendrá el elemento que está presente solo en array2. El algoritmo anterior funciona debido a la siguiente propiedad de xor "a xor a = 0" "a xor 0 = a" Espero que esto resuelva su problema. También las soluciones sugeridas anteriormente también están bien