Encuentra elemento común única de 3 matrices

Question

problema original:
tengo 3 cajas que contienen cada uno 200 monedas, dado que sólo hay una persona que ha hecho llamadas de todas las tres cajas y por lo tanto hay una moneda en cada caja que tiene las mismas huellas dactilares y el resto de todas las monedas tienen diferentes huellas dactilares. Tienes que encontrar la moneda que contiene la misma huella dactilar de las 3 cajas. Para que podamos encontrar la huella digital de la persona que realizó la llamada desde las 3 casillas.

problema Convertido:
Tienes 3 matrices que contienen 200 enteros cada uno. Dado que hay un único elemento común en estas 3 matrices. Encuentra el elemento común.
Considere resolver esto para otro espacio que no sea trivial O (1) y O (n^3) tiempo.

Answer 1

cierta mejora en la respuesta de Pelkonen:
De problema convertida en OP:

"Dado que hay uno y sólo un elemento común en estos 3 arrays."

Tenemos que ordenar solo 2 matrices y encontrar elementos comunes.

Answer 2

Si ordena todas las matrices primero O (n log n), entonces será bastante fácil encontrar el elemento común en menos de O (n^3) tiempo. Por ejemplo, puede utilizar la búsqueda binaria después de ordenarlos.

Answer 3

Usa una tabla hash para cada número entero y codifica las entradas para que sepas de qué matriz provienen; luego, busca la ranura que tiene entradas de las 3 matrices. O (n)

Answer 4

Solución O (N): utilice una tabla hash. H [i] = lista de todos los enteros en las tres matrices que se asignan a i.

Para todos H [i]> 1 compruebe si tres de sus valores son los mismos. Si es así, tienes tu solución. Puede hacer esta comprobación con la solución ingenua incluso, todavía debe ser muy rápido, o puede ordenar esos H [i] y luego se vuelve trivial.

Si sus números son relativamente pequeños, puede usar H [i] = k si aparece k veces en las tres matrices, entonces la solución es la i para la cual H [i] = 3. Si sus números son enormes , use una tabla hash sin embargo.

Puede ampliar esto para que funcione incluso si puede tener elementos que pueden ser comunes a solo dos matrices y también si puede tener elementos que repiten elementos en una de las matrices. Simplemente se vuelve un poco más complicado, pero deberías ser capaz de resolverlo por tu cuenta.

Answer 5

Usa objetos de mapeo hashtable para recuentos de frecuencia. Itere a través de las tres listas, incrementando los recuentos de ocurrencias en la tabla hash, hasta que encuentre uno con un recuento de ocurrencias de 3. Esto es O (n), ya que no se requiere clasificación.Ejemplo en Python:

def find_duplicates(*lists): 
    num_lists = len(lists) 
    counts = {} 
    for l in lists: 
    for i in l: 
     counts[i] = counts.get(i, 0) + 1 
     if counts[i] == num_lists: 
     return i 

o un equivalente, utilizando conjuntos:

def find_duplicates(*lists): 
    intersection = set(lists[0]) 
    for l in lists[1:]: 
    intersection = intersection.intersect(set(l)) 
    return intersection.pop() 

Answer 6

Si desea que el más rápido * Respuesta:

• Ordenar un array - El tiempo es N log N.
• Para cada elemento en la segunda matriz, busque la primera. Si lo encuentras, agrega 1 a una matriz complementaria; de lo contrario, agregue 0 - time es N log N, usando N espacio.
• Para cada recuento distinto de cero, copie la entrada correspondiente en la matriz temporal, compactando para que aún esté ordenada; el tiempo es N.
• Para cada elemento en la tercera matriz, busque la matriz temporal; cuando encuentres un golpe, detente. El tiempo es inferior a N N. registro

Aquí está el código en Scala que ilustra esto:

import java.util.Arrays 

val a = Array(1,5,2,3,14,1,7) 
val b = Array(3,9,14,4,2,2,4) 
val c = Array(1,9,11,6,8,3,1) 

Arrays.sort(a) 
val count = new Array[Int](a.length) 
for (i <- 0 until b.length) { 
    val j =Arrays.binarySearch(a,b(i)) 
    if (j >= 0) count(j) += 1 
} 
var n = 0 
for (i <- 0 until count.length) if (count(i)>0) { count(n) = a(i); n+= 1 } 
for (i <- 0 until c.length) { 
    if (Arrays.binarySearch(count,0,n,c(i))>=0) println(c(i)) 
} 

Con un poco más de complejidad, puede utilizar ningún espacio adicional en el costo de ser aún más destructivo de sus matrices originales, o puede evitar tocar sus matrices originales a costa de otro N espacio.

---

Editar: * como los comentarios han señalado, las tablas hash son más rápidas para las entradas no perversas. Este es el "peor caso más rápido". El peor de los casos puede no ser tan improbable a menos que uses un algoritmo de hash realmente bueno, que bien puede consumir más tiempo que tu tipo. Por ejemplo, si multiplicas todos tus valores por 2^16, el hashing trivial (es decir, simplemente usa el entero de máscara de bits como índice) colisionará cada vez en listas de menos de 64k ....

Answer 7

Let N = 200, k = 3,

1. Cree una tabla hash H con capacidad ≥ Nk.

2. Para cada elemento X en array 1, establezca H [X] en 1.

3. Para cada elemento Y en matriz 2, si Y es en H y H [Y] == 1, establecer H [y] = 2.

4. Para cada elemento de Z en matriz 3, si Z está en H y H [Z] == 2, retorno Z.

5. throw new InvalidDataGivenByInterviewerException();

O (Nk) time, O (Nk) space complexity.