Classifique uma lista de acordo com a ordem definida por outra lista

Question

Como posso classificar os elementos da lista UMA para que eles sigam a lista de Ordem de outra (Superset) B? Não assuma não duplicatas.

Por exemplo UMA pode conter [8 2 5 1] e B pode conter [5 6 9 8 7 4 1 2 3], e então eu gostaria de classificar UMA Tornar -se [5 8 1 2

Estou interessado em fazer isso com eficiência e com boa complexidade de tempo de execução.

Answer 1

Se B é um superconjunto de UMA, Eu apenas despejava UMA em uma mesa de hash, digitalize B e crie uma nova lista de onde eu insiro todos os elementos de B Isso está contido na mesa de hash. Usa o (a) memória extra e o (b) tempo de execução.

Answer 2

Aqui estão algumas idéias:

(Nas complexidades do tempo dadas, n é do tamanho de UMA e m é do tamanho de B. As complexidades do tempo não são simplificadas.)

• Para cada elemento em B, faça uma pesquisa linear de UMA Para ver se esse elemento existe nele. Nesse caso, troque -o com o primeiro elemento em UMA Isso ainda não foi colocado em posição. Complexidade do tempo: o (nm)
• O mesmo que acima, mas primeiro coloque o conteúdo de UMA em uma estrutura de pesquisa eficiente para evitar a pesquisa linear. Complexidade do tempo: o (n + m) assumindo a pesquisa de O (1)
• Ordenar B. Então, para cada elemento em UMA, encontre seu índice (que é garantido para existir) dentro B usando pesquisa binária. Registre este índice em uma matriz auxiliar do mesmo tamanho que UMA. Use essa variedade de índices como entrada para um comparador que classifica UMA. Complexidade do tempo: O ((M log m) + (n log n) + (n log n))