Dada uma lista de dados com repetições, qual método preservando a ordem dos primeiros aparecimentos tem…

Questão

Dada uma lista de dados com repetições, qual método preservando a ordem dos primeiros aparecimentos tem complexidade média linear? Cite a estrutura usada e o procedimento curto (use termos hash ou conjunto).

1. A) Um array fixo que descarta elementos repetidos conforme aparecem.
2. B) Um conjunto ordenado, que armazena elementos em ordem crescente.
3. C) Um vetor dinâmico que permite a duplicação de elementos.
4. D) Usar uma lista ligada para armazenar todos os elementos sem duplicatas.
5. E) Usar um conjunto (hash set) para rastrear elementos vistos e construir uma nova lista adicionando apenas elementos não vistos; complexidade média O(n).

✅ Resposta correta: alternativa E

Resolução passo a passo

1. O problema pede remover duplicatas de uma lista mantendo a ordem da primeira aparição, com complexidade média linear. Passo 2: Verificar cada elemento percorrendo a lista já construída custa O(n^2), porque cada checagem percorre uma parte da lista. Passo 3: Um conjunto baseado em hash (hash set) permite verificar se um elemento já foi visto em tempo médio constante, O(1). Passo 4: Basta percorrer a lista original uma única vez: para cada elemento, consulta-se o conjunto; se ele não estiver, adiciona-se ao conjunto e à nova lista; se já estiver, descarta-se. Passo 5: Como são n elementos, cada um com custo médio O(1), o total é O(n) em média. A ordem é preservada porque a nova lista é montada na ordem de leitura. Passo 6: A alternativa A está errada, pois um array fixo não guarda o histórico de elementos vistos e não identifica repetições sem uma busca. Passo 7: A alternativa B está errada, pois um conjunto ordenado reorganiza os elementos em ordem crescente, perdendo a ordem original, e cada operação custa O(log n). Passo 8: A alternativa C está errada, pois um vetor dinâmico apenas cresce ao ser preenchido e não remove duplicatas. Passo 9: A alternativa D está errada, pois uma lista ligada sem controle dos vistos exige percorrer a lista inteira para detectar repetições, resultando em O(n^2). Passo 10: Portanto, o gabarito E está correto e é a única alternativa que combina estrutura de busca rápida com a construção ordenada da nova lista.

💡 Dica: Considere o uso de um conjunto para armazenar os elementos únicos.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Para detectar duplicatas em uma lista de n dados, qual abordagem tem melhor complexidade média: comparar cada par…
• Ao projetar um algoritmo que agrupa registros de alunos por turma e precisa manter a ordem de inserção enquanto permite…
• Em um algoritmo que processa uma lista de alunos como dados e precisa evitar registros duplicados, qual estrutura de…
• Considere uma lista ligada não ordenada com n elementos. Qual estratégia que usa uma estrutura auxiliar permite remover…
• Para detectar duplicatas em uma matriz de registros 'dados' onde cada registro tem uma chave 'id', qual estrutura de…
• Você precisa armazenar uma coleção onde testar a existência de um elemento seja muito rápido e a ordem dos elementos não…

Todas as questões de Listas e grafos