Valores em comum de duas listas
A missão
Problema
Dadas duas listas de valores, retorne os valores que aparecem nas duas. Cada valor em comum aparece uma vez no resultado, mesmo quando uma das listas o repete, e o resultado segue a ordem em que os valores aparecem pela primeira vez na primeira lista.
Exemplos
Input: a = [1, 2, 2, 1], b = [2, 2]
Output: [2]
Por quê: um valor em comum é informado uma vez, não importa quantas vezes se repita
Input: a = [4, 9, 5], b = [9, 4, 9, 8, 4]
Output: [4, 9]
Por quê: a ordem vem da primeira lista, não da segunda
Input: a = [1, 2], b = [3]
Output: []
Por quê: edge case: as listas não têm nada em comum
Dicas
0 / 3
Comparar cada valor da primeira lista com toda a segunda lista dá a resposta certa, mas com releitura demais. Pergunte-se o que você poderia preparar uma vez, antes de a comparação começar.
A pergunta feita em cada elemento da primeira lista é um teste de pertencimento na segunda lista, e existe uma estrutura cujo único trabalho é responder a isso em tempo constante.
Carregue a segunda lista em um conjunto. Percorra a primeira lista uma vez e fique com um valor quando o conjunto o contiver e você ainda não o tiver informado. Registre o que já informou em um segundo conjunto, para que duplicados na primeira lista não gerem saída duplicada.
- Tempo-alvo
- O(n + m)
- Espaço-alvo
- O(m)
Solução
Carregar a segunda lista em um conjunto (set) transforma cada uma das n comparações em uma busca em tempo constante, em vez de uma varredura. Percorrer a primeira lista em ordem faz a ordem da saída sair de graça, e um segundo conjunto de valores já informados mantém as repetições de fora, sem ordenação nem pós-processamento. O tempo é O(n + m) em média, e o espaço é O(m) para o conjunto de busca mais os valores informados.
def shared_values(a, b):
pool = set(b) # membership in b is now a constant-time test
out, reported = [], set()
for x in a:
if x in pool and x not in reported:
out.append(x) # first appearance in a fixes the order
reported.add(x)
return out
print(shared_values([1, 2, 2, 1], [2, 2])) # -> [2]
print(shared_values([4, 9, 5], [9, 4, 9, 8, 4])) # -> [4, 9]
print(shared_values([1, 2], [3])) # -> []Travou na ideia, e não no código? O básico de tabelas hash explica isso.