Ordenar una lista de acuerdo con la orden definido por otra lista

Question

¿Cómo puedo ordenar los elementos de la lista para que sigan el orden de otra lista (superconjunto) B ? Suponga que no hay duplicados.

por ejemplo. A podría contener [8 2 5 1] y B podría contener [5 6 9 8 7 4 1 2 3], y así me gustaría sort a a convertirse en [5 8 1 2]

Estoy interesado en maneras de hacer esto de manera eficiente y con buena complejidad en tiempo de ejecución.

Answer 1

Si B es un superconjunto de , que acababa de volcar en una tabla hash, exploración B y crear una nueva lista en la que insertar todos los elementos de B que se encuentra en la tabla hash. Usos O (a) de memoria adicional y O (b) tiempo de ejecución.

Answer 2

Aquí están algunas ideas:

(En las complejidades de tiempo dado, n es el tamaño de A y m es el tamaño de B . Las complejidades de tiempo no se simplifican.)

• Para cada elemento de B , hacer una búsqueda lineal de para ver si existe ese elemento en ella. Si es así, intercambio con el primer elemento de que aún no ha sido puesto en posición. Complejidad de tiempo: O (nm)
• Igual que el anterior, pero en primer lugar poner el contenido de en una estructura de consulta eficiente para evitar la búsqueda lineal. Tiempo complejidad: O (n + m) suponiendo O (1) Buscar
• Ordenar B . Entonces, para cada elemento de , encontrar su índice (que está garantizado de existir) dentro de B mediante la búsqueda binaria. Registre este índice en una matriz auxiliar del mismo tamaño que A . Utilice esa matriz de índices como entrada a un comparador que tipo A . Tiempo complejidad: O ((m log m) + (n log n) + (n log n))