C言語で重複を削除する配列の方法は何ですか

1年 ago
光, 明
2 minutes

C言語では、配列の重複を除去するために次の手法を使用できます：

  1. 配列を二重ループで繰り返し、各要素とその後の要素を比較し、等しければ、その後の要素を削除します。この方法の時間計算量はO(n^2)と高くなります。
int removeDuplicates(int arr[], int n)
{
    int i, j, k;
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n;) {
            if (arr[j] == arr[i]) {
                for (k = j; k < n; k++) {
                    arr[k] = arr[k + 1];
                }
                n--;
            } else {
                j++;
            }
        }
    }
    return n;
}
  1. まず配列をソートし、次に配列を繰り返し処理して重複した要素を削除する。この方法の時間計算量は、ソートアルゴリズムの複雑度に依存し、通常 O(nlogn) となる。
#include <stdio.h>
#include <stdlib.h>

int cmpfunc(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int removeDuplicates(int arr[], int n) {
    int i, j;
    if (n == 0 || n == 1)
        return n;
    qsort(arr, n, sizeof(int), cmpfunc);
    i = 0;
    for (j = 1; j < n; j++) {
        if (arr[j] != arr[i]) {
            i++;
            arr[i] = arr[j];
        }
    }
    return i + 1;
}

int main() {
    int arr[] = {1, 2, 2, 3, 3, 3, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = removeDuplicates(arr, n);
    printf("Array after removing duplicates: ");
    for (int i = 0; i < result; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}
  1. ハッシュ表を用いて配列に出現した要素を記録する。配列を走査するとき、現在の要素がハッシュ表に出現しているかどうかを判断する。もし出現していなければ、ハッシュ表に追加し、元の配列に残す。この方法の時間計算量は O(n) だが、ハッシュ表の保存用に追加の領域が必要となる。
#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

void removeDuplicates(int arr[], int n) {
    int hash[MAX_SIZE] = {0};
    int i, j;
    for (i = 0; i < n; i++) {
        if (hash[arr[i]] == 0) {
            hash[arr[i]] = 1;
            printf("%d ", arr[i]);
        }
    }
}

int main() {
    int arr[] = {1, 2, 2, 3, 3, 3, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Array after removing duplicates: ");
    removeDuplicates(arr, n);
    return 0;
}
bannerAds