Edição didática em português. O código e suas saídas preservam o original.
Exercícios de arrays em C: remova duplicados
Remova duplicados de um array ordenado em C com dois índices. Guarde os valores únicos no próprio array e imprima a quantidade e os elementos.
Leia N e um array de N inteiros em ordem não decrescente. Remova os valores repetidos sem criar outro array. Mantenha uma ocorrência de cada valor e imprima o novo comprimento e os elementos únicos.
Use um índice de leitura e outro de escrita. Se o valor lido for diferente do último mantido, copie-o para arr[write] e avance a escrita. Com N = 1 nada muda; se todos forem iguais, resta um valor.
Entrada
Primeira linha: N. Segunda linha: N inteiros em ordem não decrescente.
Saída
Primeira linha: quantidade de valores únicos. Segunda linha: esses valores separados por espaços.
Restrições
- 1 <= N <= 1000
- -1000 <= arr[i] <= 1000
- Entrada em ordem não decrescente.
- Use O(1) de memória auxiliar.
Dicas
- Mantenha o primeiro elemento: N é pelo menos um.
- Compare cada valor com o último mantido.
Código C
#include <stdio.h>
#define MAX_N 1000
int remove_duplicates(int arr[], int n) {
// TODO: Compact unique values into arr[0..write-1] and return write.
(void)arr;
return n;
}
int main(void) {
int n;
if (scanf("%d", &n) != 1 || n < 1 || n > MAX_N) return 1;
int arr[MAX_N];
for (int i = 0; i < n; ++i) {
if (scanf("%d", &arr[i]) != 1 || arr[i] < -1000 || arr[i] > 1000) return 1;
if (i > 0 && arr[i] < arr[i - 1]) return 1;
}
int length = remove_duplicates(arr, n);
printf("%d\n", length);
for (int i = 0; i < length; ++i) {
printf("%d%c", arr[i], i == length - 1 ? '\n' : ' ');
}
return 0;
}Solução e explicação
Inicie write em 1. Percorra o array a partir de read = 1; copie arr[read] para arr[write] apenas se diferir de arr[write - 1] e incremente write.
Imprima write e o prefixo com esse comprimento. O algoritmo usa O(N) de tempo e O(1) de memória auxiliar.
Código da solução
#include <stdio.h>
#define MAX_N 1000
int remove_duplicates(int arr[], int n) {
int write = 1;
for (int read = 1; read < n; ++read) {
if (arr[read] != arr[write - 1]) {
arr[write] = arr[read];
++write;
}
}
return write;
}
int main(void) {
int n;
if (scanf("%d", &n) != 1 || n < 1 || n > MAX_N) return 1;
int arr[MAX_N];
for (int i = 0; i < n; ++i) {
if (scanf("%d", &arr[i]) != 1 || arr[i] < -1000 || arr[i] > 1000) return 1;
if (i > 0 && arr[i] < arr[i - 1]) return 1;
}
int length = remove_duplicates(arr, n);
printf("%d\n", length);
for (int i = 0; i < length; ++i) {
printf("%d%c", arr[i], i == length - 1 ? '\n' : ' ');
}
return 0;
}Perguntas frequentes
Por que o código e a saída continuam em inglês?
Palavras-chave, identificadores e textos verificados pelos testes são preservados para não alterar o programa. As explicações e os controles estão traduzidos.