Escreva uma função que receba uma lista e retorne uma nova lista sem elementos duplicados. Lembre que os elementos duplicados não precisam aparecer em posições consecutivas. Dica: use um dicionário
Passo 1
O que o enunciado pede:
- Escrever uma função que receba uma lista e retorne uma nova lista sem elementos duplicados.
- Os elementos duplicados podem não estar em posições consecutivas (ou seja, a deduplicação deve considerar toda a lista).
- Dica fornecida: usar um dicionário.
Informações relevantes:
- Entrada: uma lista (pode conter qualquer tipo de objetos).
- Saída: uma nova lista contendo cada valor que apareceu na entrada apenas uma vez.
- Não foi explicitado no enunciado, mas adotarei que a função deve preservar a ordem da primeira ocorrência de cada elemento (comportamento geralmente desejado em provas/questões práticas).
- Atenção a tipos não-hasháveis (por exemplo: listas, dicionários) — estes não podem ser usados diretamente como chaves de dicionário em Python.
Passo 2
Ideia geral e por que usar um dicionário:
- Um dicionário (mapa/hashtable) associa chaves a valores e permite verificar rapidamente se uma chave já existe.
- Em Python, testar se uma chave está no dicionário tem custo médio
por operação, então percorrer a lista inteira e marcar elementos já vistos usando um dicionário produz complexidade média , onde é o tamanho da lista. - Estratégia: percorrer a lista da esquerda para a direita; para cada elemento:
- se ainda não foi visto, adicioná-lo à lista de resultado e marcar como visto no dicionário;
- se já foi visto, pular.
- Isso preserva a ordem de primeira aparição.
Explicando os termos:
- Dicionário: estrutura que guarda pares chave→valor. Ex.: em Python,
seen = {}cria um dicionário vazio. - Chave hashável: para ser usada numa chave de dicionário, o objeto precisa ser imutável e ter um hash (ex.: números, strings, tuplas contendo apenas objetos hasháveis). Objetos como listas não são hasháveis e causam
TypeErrorao tentar usá-los como chave. - Complexidade: “médio
” significa que o tempo cresce linearmente com o número de elementos, na maioria dos casos.
Passo 3
Implementação simples (caso todos os elementos sejam hasháveis):
- Escrevo a versão direta e explico linha a linha.
Código:
def unique_preserve_order_hashable(lst):
seen = {}
out = []
for x in lst:
if x not in seen:
seen[x] = True
out.append(x)
return out
Explicação passo a passo do código:
seen = {}cria um dicionário vazio que usaremos para lembrar quais valores já apareceram.out = []será a lista de saída sem duplicatas.for x in lst:percorre cada elemento da lista de entrada, na ordem.if x not in seen:verifica sexjá foi registrado; essa verificação é eficiente para chaves hasháveis.seen[x] = Truemarcaxcomo visto (o valor armazenado não importa; poderia serNone).out.append(x)adicionaxao resultado somente na primeira vez que aparece.return outdevolve a lista sem duplicatas, na ordem de primeira aparição.
Exemplo prático:
- Entrada:
['a', 'b', 'a', 'c', 'b'] - Passos: adiciona
'a'→out = ['a']; adiciona'b'→out = ['a','b']; ignora'a'; adiciona'c'→out = ['a','b','c']; ignora'b'. - Saída:
['a', 'b', 'c'].
Complexidade desta versão: tempo médio
, memória adicional aproximadamente
onde
é número de únicos (para o dicionário e a lista de saída).
Passo 4
Tratando elementos não-hasháveis (versão robusta):
- Se a lista pode conter elementos não-hasháveis (ex.: outras listas, dicionários), a verificação
if x not in seen:lançaTypeError. - Solução prática e simples: tentar usar o dicionário e, se ocorrer
TypeError, comparar esse elemento com uma lista separada de elementos não-hasháveis já vistos (comparação por igualdade==). Isso mantém corretude; porém, se houver muitos elementos não-hasháveis idênticos, a verificação por igualdade custa tempo linear naquela sublista (podendo levar a comportamentono pior caso), mas é necessário a menos que se imponha restrição de tipos.
Código robusto:
def unique_preserve_order(lst):
seen = {}
seen_unhashable = []
out = []
for x in lst:
try:
if x not in seen:
seen[x] = True
out.append(x)
except TypeError:
# x não é hashável: procurar por igualdade entre os não-hasháveis já vistos
found = False
for y in seen_unhashable:
if x == y:
found = True
break
if not found:
seen_unhashable.append(x)
out.append(x)
return out
Explicação passo a passo:
seenregistra os elementos hasháveis já vistos.seen_unhashableguarda os representantes dos elementos não-hasháveis já vistos; usamos comparação==para detectar duplicatas entre eles.- No loop, tenta-se
if x not in seen:; sexfor não-hashável, isto disparaTypeErrore entra no blocoexcept. - No bloco
except, faz-se uma busca linear emseen_unhashablepor um elementoytal quex == y; se não encontrado, acrescenta-sexaseen_unhashableeout. - Dessa forma, tanto tipos hasháveis quanto não-hasháveis são tratados corretamente, e a ordem de primeira aparição é preservada.
Passo 5
Atalhos e alternativas úteis
- Em Python, se tiver certeza de que todos os elementos são hasháveis, uma solução compacta e idiomática é:
list(dict.fromkeys(lst))
Explicação: . Falha se houver elementos não-hasháveis.
dict.fromkeys(lst) cria um dicionário cujas chaves são os elementos de lst na ordem de aparição; list(...) sobre as chaves preserva essa ordem. Complexidade média
- Se não for necessário preservar ordem, pode-se converter para conjunto:
list(set(lst)), mas isso perde ordem e não é estável.
Passo 6
Resumo e recomendação final
- Se elementos são todos hasháveis e deseja preservar ordem: use
list(dict.fromkeys(lst))ou a implementação comseenmostrada no Passo 3. - Se a lista pode conter elementos não-hasháveis e a preservação de ordem é importante: use a implementação robusta do Passo 4.
- Complexidade típica esperada: médio
para hasháveis; pior caso se muitos elementos não-hasháveis forem presentes e precisam ser comparados por igualdade.
Força aí — respira, copia a função que segue e testa com alguns exemplos; isso resolve a maioria das questões de prova sobre eliminar duplicatas preservando ordem.
Resposta
def unique_preserve_order(lst):
seen = {}
seen_unhashable = []
out = []
for x in lst:
try:
if x not in seen:
seen[x] = True
out.append(x)
except TypeError:
found = False
for y in seen_unhashable:
if x == y:
found = True
break
if not found:
seen_unhashable.append(x)
out.append(x)
return out
seen = {}
seen_unhashable = []
out = []
for x in lst:
try:
if x not in seen:
seen[x] = True
out.append(x)
except TypeError:
found = False
for y in seen_unhashable:
if x == y:
found = True
break
if not found:
seen_unhashable.append(x)
out.append(x)
return out