Nederlandse leereditie

C-arrayoefeningen: dubbele waarden verwijderen

Verwijder dubbele waarden uit een gesorteerde C-array met twee indexen. Bewaar unieke waarden in dezelfde array en druk hun aantal en de waarden af.

Openen in de compiler

C-arrayoefeningen: dubbele waarden verwijderen — Verwijder dubbele waarden uit een gesorteerde C-array met twee indexen. Bewaar unieke waarden in dezelfde array en druk hun aantal en de waarden af.

Lees N en een array met N gehele getallen in niet-afnemende volgorde. Verwijder herhaalde waarden zonder een tweede array te maken. Bewaar elke waarde één keer en druk de nieuwe lengte en de unieke elementen af.

Gebruik een leesindex en een schrijfindex. Verschilt de gelezen waarde van de laatst bewaarde waarde, kopieer die dan naar arr[write] en verhoog de schrijfindex. Bij N = 1 verandert niets; bij gelijke waarden blijft er één over.

Invoer

Eerste regel: N. Tweede regel: N gehele getallen in niet-afnemende volgorde.

Uitvoer

Eerste regel: aantal unieke waarden. Tweede regel: deze waarden, gescheiden door spaties.

Voorwaarden

1 <= N <= 1000
-1000 <= arr[i] <= 1000
De invoer staat in niet-afnemende volgorde.
Gebruik O(1) extra geheugen.

Hints

Bewaar het eerste element: N is minstens één.
Vergelijk met de laatst bewaarde waarde.

Broncode

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

Openen in de compiler

Uitleg van de oplossing

Begin met write = 1. Lees vanaf read = 1; als arr[read] verschilt van arr[write - 1], kopieer het naar arr[write] en verhoog write.

Druk write en het beginstuk van die lengte af. De looptijd is O(N), het extra geheugen O(1).

Oplossingscode

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

Veelgestelde vragen

Waarom blijven code en sommige resultaten Engels?

C-sleutelwoorden, namen, programmacommentaar en verwachte uitvoer blijven gelijk aan het origineel om uitvoerbare code en consistente tests te behouden. Uitleg en instructies zijn vertaald.