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

• Projete um algoritmo in-place, em pseudocódigo, que receba um vetor A de n números distintos e um inteiro k (1 = k = n)…
• Escreva um algoritmo em pseudocódigo que, dado um vetor V de n inteiros, construa dois vetores preservando a ordem…
• Projete um algoritmo, em pseudocódigo, que receba uma lista ligada simples L com n nós e remova todos os nós cujos…
• Projete um algoritmo em pseudocódigo que, dado um vetor V de n inteiros e um inteiro k, determine se existem índices i <…
• Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros, encontre o comprimento do maior subvetor…
• Projete, em pseudocódigo, um algoritmo que receba um vetor A[0..n-1] de inteiros e um inteiro alvo t, e retorne dois…

Todas as questões de Decomposição