Projete em pseudocódigo um algoritmo que remova, in-place, todas as ocorrências de um valor v em um vetor A de…

Questão

Projete em pseudocódigo um algoritmo que remova, in-place, todas as ocorrências de um valor v em um vetor A de comprimento n, mantendo a ordem relativa dos demais elementos. Descreva complexidade temporal e espacial e trate casos limites.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo (preservando ordem, in-place): i ? 0 para j de 0 até n-1 faça se A[j] ? v então A[i] ? A[j] i ? i + 1 fim para // opcional: ajustar tamanho lógico do vetor para i retorne i // novo comprimento Complexidade: - Temporal: O(n), pois cada elemento é examinado uma vez. - Espacial adicional: O(1), pois usa apenas índices auxiliares. Casos limites e observações: - Vetor vazio (n = 0): retorna 0, nada a mover. - Todos os elementos iguais a v: i permanece 0; resultado tamanho 0. - Nenhum elemento igual a v: cópia overwrites preserva ordem e i = n. - O algoritmo é estável (mantém ordem relativa) e realiza remoção in-place sem buffers adicionais.

Explicação

O algoritmo proposto utiliza uma abordagem eficiente para percorrer o vetor e mover os elementos que não são iguais a v para o início, garantindo que a ordem relativa dos elementos seja mantida. A complexidade temporal de O(n) é alcançada ao visitar cada elemento apenas uma vez, enquanto a complexidade espacial adicional de O(1) é obtida ao usar apenas variáveis auxiliares para controle de índices. Os casos limites são tratados adequadamente, assegurando que o algoritmo funcione corretamente em diferentes cenários, como vetores vazios ou com todos os elementos iguais a v.

Raio-X da questão

Questões parecidas com resolução

• Na creche, a equipe organiza o lanche das salas Girassol e Nuvem. A tabela mostra o que já foi feito: | Tarefa | Sala…
• Em um canavial, um gráfico de barras descrito em palavras mostra os pontos secos encontrados em cada trecho: trecho A, 2…
• Durante uma atividade sobre vulcões, Bia precisa montar um aviso com três informações: presença de fumaça, tremores e…
• Antes da aula, Davi precisa arrumar sua mochila. Como Davi pode fazer isso em até três partes, uma de cada vez?
• — Não basta publicar as imagens das cartas — alertou a coordenadora do arquivo municipal ao planejar uma plataforma…
• Projete um algoritmo, em passos claros, para fragmentar um arquivo em pacotes, numerá-los, aplicar checksum e…

Todas as questões de Decomposição