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 O(1) por operação, então percorrer a lista inteira e marcar elementos já vistos usando um dicionário produz complexidade média O(n), onde n é 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 TypeError ao tentar usá-los como chave.
  • Complexidade: “médio O(n)” 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 se x já foi registrado; essa verificação é eficiente para chaves hasháveis.
  • seen[x] = True marca x como visto (o valor armazenado não importa; poderia ser None).
  • out.append(x) adiciona x ao resultado somente na primeira vez que aparece.
  • return out devolve 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 O(n), memória adicional aproximadamente O(k) onde k é 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ça TypeError.
  • 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 comportamento O(n^2) no 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:
  • seen registra os elementos hasháveis já vistos.
  • seen_unhashable guarda 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:; se x for não-hashável, isto dispara TypeError e entra no bloco except.
  • No bloco except, faz-se uma busca linear em seen_unhashable por um elemento y tal que x == y; se não encontrado, acrescenta-se x a seen_unhashable e out.
  • 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: 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 O(n). Falha se houver elementos não-hasháveis.
  • 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 com seen mostrada 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 O(n) para hasháveis; pior caso O(n^2) 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

Exercícios relacionados