Édition pédagogique en français

Exercices de tableaux en C : supprimer les doublons

Supprimez les doublons d’un tableau trié en C avec deux indices. Gardez les valeurs uniques dans le même tableau, puis affichez leur nombre et leurs valeurs.

Ouvrir dans le compilateur

Exercices de tableaux en C : supprimer les doublons — Supprimez les doublons d’un tableau trié en C avec deux indices. Gardez les valeurs uniques dans le même tableau, puis affichez leur nombre et leurs valeurs.

Lisez N et un tableau de N entiers triés par ordre croissant au sens large. Supprimez les valeurs répétées sans créer de second tableau. Gardez une occurrence de chaque valeur et affichez la nouvelle longueur et les éléments uniques.

Utilisez un indice de lecture et un indice d’écriture. Si la valeur lue diffère de la dernière conservée, copiez-la dans arr[write] et avancez l’écriture. Pour N = 1, rien ne change ; si toutes les valeurs sont égales, il en reste une.

Entrée

Première ligne : N. Deuxième ligne : N entiers triés par ordre croissant au sens large.

Sortie

Première ligne : nombre de valeurs uniques. Deuxième ligne : ces valeurs séparées par des espaces.

Contraintes

1 <= N <= 1000
-1000 <= arr[i] <= 1000
Le tableau est trié par ordre croissant, avec répétitions possibles.
Utilisez O(1) de mémoire auxiliaire.

Indices

Conservez le premier élément : N vaut au moins un.
Comparez avec la dernière valeur conservée.

Code source

#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;
}

Ouvrir dans le compilateur

Explication de la solution

Initialisez write à 1. Parcourez depuis read = 1 ; si arr[read] diffère de arr[write - 1], copiez-le dans arr[write] et incrémentez write.

Affichez write et le préfixe de cette longueur. Le temps est O(N) et la mémoire auxiliaire O(1).

Code de la solution

#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;
}

Questions fréquentes

Pourquoi le code et certains résultats restent-ils en anglais ?

Les mots-clés C, les identifiants, les commentaires du programme et les sorties attendues restent ceux de la version originale pour conserver un code exécutable et des tests cohérents. Les explications et les consignes sont traduites.