Encuentra el mapeo único entre los elementos de dos matrices de tamaño mismos

Question

poco me preguntaron esta pregunta en una entrevista:

Hay dos matrices de tamaño 'n' cada uno. Una matriz tiene nueces, la otra tiene tornillos. Cada tuerca se ajusta exactamente a un perno y viceversa. Cuando compara una tuerca con un perno, obtiene uno de los 3 resultados: apretado, suelto, encaja.

¿Cómo se puede encontrar eficientemente el mapeo único?

La ordenación no es posible en ninguno de los juegos. Nunca se sabe si b1 es más pequeño que b2 o
n1 es más pequeño que n2. Donde n1, n2 son nueces y b1, b2 son pernos. Lo único que puede hacer es comparar una tuerca con un perno y obtener un resultado: apretado, ajuste, suelto.

Answer 1

El quicksort como algoritmo hace el trabajo:

1. escogerán aleatoriamente una tuerca n y utilizarlo como pivote para dividir el conjunto de pernos B en tres conjuntos: apretado (B1), suelto (B2), ataques .
2. Marque el perno de ajuste como b. Ahora usa este perno como pivote para dividir las tuercas establecidas en N\n en dos conjuntos: apretados (N1) o sueltos (N2).
3. Ahora tienen tres pares: N1 y B1, n y b, N2 y B2. Todos ellos son del mismo tamaño. Puede hacer la misma partición recursivamente en (N1,B2) y (N2,B1) y puede obtener la respuesta final.

Es obvio que la complejidad es O(N log N), lo mismo que quicksort.

Answer 2

Tome una tuerca N0 y compárela con todos los pernos. Con la información resultante, podemos dividir la matriz de pernos en [bolts smaller than B0] + B0 + [bolts larger than B0]. Siempre hay un único B0 que se ajusta a N0 según la declaración de la pregunta.

A continuación, tome la siguiente tuerca N1 y compárela con B0. Si el resultado es "ajustado", buscamos la mitad más pequeña como hicimos anteriormente con N0. De lo contrario, hacemos lo mismo pero con la mitad más grande. Hacer esto dividirá aún más una de las dos mitades en 2.

Continúe haciendo esto hasta que haya trabajado con todas las tuercas. Esto es equivalente a quicksort. El caso promedio es O (N logN), pero existe la obvia complejidad de peor caso de O (N^2) cuando la lista ya está "clasificada".

Answer 3

Para los análisis formales (incluyendo la clasificación rápida) ver http://www.wisdom.weizmann.ac.il/~naor/PUZZLES/nuts_solution.html y http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-nutsbolts.pdf