Por lo tanto, para aclarar la cuestión:Dos conjuntos de elementos. Cada elemento del conjunto A un partido único en el conjunto B. ajuste de cada elemento del conjunto A al punto B en conjunto en O (nlogn) Tiempo de
Conjunto A y B Conjunto cada elemento en el conjunto A tiene un compañero en el conjunto B no puede ordenar ninguno de los conjuntos basándose en compararlo con miembros del mismo conjunto, es decir, cada elemento b de B es indistinguible de cualquier otro b del conjunto B (del mismo modo para A). cuando Ai se combina con Bi, puede decir si Bi > Ai
, Bi < Ai
o Bi = Ai
. diseñe un algoritmo con tiempo de ejecución O (nlogn).
La respuesta obvia con el tiempo cuadrático es trivial y no útil, aunque es lo mejor que he encontrado hasta ahora. El registro (n) me hace pensar que debería estar utilizando la recursividad o un árbol binario de algún tipo, pero no estoy seguro de cómo podría crear un árbol binario sin poder comparar elementos del mismo conjunto. Además, no estoy seguro de cómo utilizar una llamada recursiva con un efecto mayor que solo ejecutar bucles anidados. Algún consejo sería de gran aprecio.
Ordénelas y utilice un solo bucle para recorrer todos los elementos. Si tiene una estructura de datos establecida desde el principio, puede sacar el iterador y recorrerlo. – nhahtdh
Entonces, ¿está diciendo que las A y las B no son comparables entre sí, pero puede comparar cada A con cada B y necesita encontrar pares tales que 'A == B'? – verdesmarald
Este problema es básicamente idéntico al problema de las tuercas y tornillos coincidentes según lo establecido por gowaayacct. Gracias por la atención sin embargo. – slmyers