配列から重複を取り除く場合、C言語ではどのように処理しますか。

1年 ago
綾乃, 一希
2 minutes

C 言語では、次の複数の方法で配列の重複除去を行うことができます。

  1. 二重ループで配列を走査し、各要素がその後の要素と重複しているかを判断して、重複している要素を削除します。この方法は時間計算量が大きく、O(n^2) です。コードの例を以下に示します。
#include <stdio.h>

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

int main() {
    int arr[] = {1, 2, 3, 4, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    n = removeDuplicates(arr, n);

    printf("Array after removing duplicates: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}
  1. ネイティブの配列やハッシュを利用して元配列を走査し、要素を新しい配列やハッシュに保存する。その際、要素がすでに存在したらスキップする。このメソッドの計算量は O(n) 時間となります。以下にサンプルコードを示します。
#include <stdio.h>

int removeDuplicates(int arr[], int n) {
    int temp[n];
    int j = 0;

    for (int i = 0; i < n; i++) {
        int duplicate = 0;
        for (int k = 0; k < j; k++) {
            if (arr[i] == temp[k]) {
                duplicate = 1;
                break;
            }
        }
        if (!duplicate) {
            temp[j++] = arr[i];
        }
    }

    for (int i = 0; i < j; i++) {
        arr[i] = temp[i];
    }

    return j;
}

int main() {
    int arr[] = {1, 2, 3, 4, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    n = removeDuplicates(arr, n);

    printf("Array after removing duplicates: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}
  1. ソートされた配列を反復処理して、隣接する重複する要素を削除する。この手法の時間複雑度は、ソートアルゴリズムの複雑度によって決まり、通常は O(n log n) となる。次のコードは一例である。
#include <stdio.h>
#include <stdlib.h>

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

int removeDuplicates(int arr[], int n) {
    qsort(arr, n, sizeof(int), compare);

    int j = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] != arr[i + 1]) {
            arr[j++] = arr[i];
        }
    }

    return j;
}

int main() {
    int arr[] = {1, 2, 3, 4, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    n = removeDuplicates(arr, n);

    printf("Array after removing duplicates: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

これらの3つのメソッドはすべて配列の重複を削除できますが、どのメソッドを選択するかは実際のニーズと性能要件によって決まります。

bannerAds