Ordinare un elenco secondo l'ordine definito da un altro elenco

Question

Come posso sorta gli elementi della lista A in modo che seguano l'ordinamento di un altro (superset) Lista B ? Assumere duplicati.

es. A potrebbe contenere [8 2 5 1] e B potrebbe contenere [5 6 7 8 9 4 1 2 3], e così mi piacerebbe sorta a per diventare [5 8 1 2]

Sono interessato a modi di fare questo in modo efficiente e con una buona complessità di esecuzione.

Answer 1

Se B è un superset di A , che avevo appena discarica A in una hash-table, scan B e creare un nuovo elenco in cui inserisco ogni elemento da B che è contenuto nella tabella hash. Usi O (a) memoria aggiuntiva e O (b) fase di esecuzione.

Answer 2

Ecco alcune idee:

(Nelle complessità di tempo dato, n è la dimensione di A e m è la dimensione di B . La complessità di tempo non sono semplificate.)

• Per ogni elemento in B , fare una ricerca lineare di A per vedere se questo elemento esiste in esso. Se è così, di swap con il primo elemento in A che non è ancora stato messo in posizione. Tempo complessità: O (nm)
• Come sopra, ma in primo luogo mettere il contenuto di A in una struttura di ricerca efficace per evitare la ricerca lineare. Tempo complessità: O (n + m) assumendo O (1) ricerca
• Ordina B . Poi, per ogni elemento in A , trovare il suo indice (che è garantito per esistere) all'interno di B con ricerca binaria. Registrare questo indice in un array ausiliario della stessa dimensione A . Utilizzare tale matrice di indici come ingresso ad un comparatore che sorta A . Tempo complessità: O ((m log m) + (n log n) + (n log n))