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

• Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
• Explique como você organizaria uma lista de tarefas diárias, mencionando como as prioridades podem influenciar a…
• Antes de ir à feira, Bia anotou: pão, bananas e sabonete. Que objeto do dia a dia é esse e como Bia pode mudar a ordem…
• No mapa da sala, há círculos para a porta, a mesa da professora, a estante e o quadro. As linhas ligam porta-mesa…
• — A mensagem não chegou ao abrigo do bairro Serra — avisou uma moradora pelo rádio comunitário. Após a enchente, a…
• — O painel da praça ficou cheio de bilhetes sobre lâmpadas apagadas — observou Caio, voluntário do bairro. Em cada…

Todas as questões de Listas e grafos