配列に値の重複がないことを調べる | Programming Place Plus C言語編 逆引き

トップページC言語編逆引き

このページの概要

以下は目次です。

目的

配列の要素の中に、同じ値をもった要素がないことを確認したいとします。

要素の型は、同じ値かどうかを「==」で調べられるものであれば、何でも構いません。

array_is_unique という関数にすることを考えます。引数には、配列(を指すポインタ)と、その配列の要素数を渡し、戻り値は、重複がなければ true、重複があれば false を返すようにします。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int main(void)
{
    int array1[] = {7, 2, 6, 1, 4, 9, 8};
    int array2[] = {7, 2, 6, 7, 4, 9, 8};

    printf("%d\n", array_is_unique(array1, SIZE_OF_ARRAY(array1)));
    printf("%d\n", array_is_unique(array2, SIZE_OF_ARRAY(array2)));
}

望む結果は、次のとおりです。

1
0

SIZE_OF_ARRAYマクロは、配列の要素数を取得するものです。詳細は「逆引き 配列の要素数を求める」を参照してください。

方法①(総当たりで調べる)

二重のループをつくって、すべての要素を総当たりで調べて、重複を探します。

この方法はいつでも使えます。

#include <stdbool.h>
#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

/*
    配列内に値の重複がないかどうかを返す

    引数
        array: 対象の配列
        size:  array の要素数
    戻り値
        重複がなければ true、重複があれば false
*/
bool array_is_unique(const int* array, size_t size)
{
    for (size_t i = 0; i < size - 1; ++i) {
        for (size_t j = i + 1; j < size; ++j) {
            if (array[i] == array[j]) {
                return false;
            }
        }
    }

    return true;
}

int main(void)
{
    int array1[] = {7, 2, 6, 1, 4, 9, 8};
    int array2[] = {7, 2, 6, 7, 4, 9, 8};

    printf("%d\n", array_is_unique(array1, SIZE_OF_ARRAY(array1)));
    printf("%d\n", array_is_unique(array2, SIZE_OF_ARRAY(array2)));
}

実行結果:

1
0

array[i] と array[j] の比較を繰り返し、1度でも同じ値になることがあったら、重複があると判断できます。

変数 i は外側の for文で制御しており、変数 j は内側の for文で制御していますから、j のほうが次々と値が変化します。

注意すべき点は2つです。

1つは、変数 j の初期値を i + 1 で始めることです。i == j となる瞬間ができないようにしなければなりません。i == j のときに、array[i] と array[j] を比較したら、当然同じ値なので、誤って重複していると判定してしまいます。

もう1つは、j は末尾の要素の位置(array[size-1])まで進むのに対して、i はその1つ手前までしか進まないことです。j の初期値は i + 1 なので、i を size - 1 まで進めてしまうと、array[size] の位置を参照してしまいます(範囲外アクセス)。

方法②(ソートされた状態を利用する)

配列がソートされているのなら、その状態を利用して効率を上げられます。

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int compare_int(const void* a, const void* b)
{
    int a_num = *(int*)a;
    int b_num = *(int*)b;

    return a_num - b_num;
}

/*
    配列内に値の重複がないかどうかを返す

    ※ソート済みでなければならない

    引数
        array: 対象の配列
        size:  array の要素数
    戻り値
        重複がなければ true、重複があれば false
*/
bool array_is_unique(const int* array, size_t size)
{
    for (size_t i = 0; i < size - 1; ++i) {
        if (array[i] == array[i + 1]) {
            return false;
        }
    }

    return true;
}

int main(void)
{
    int array1[] = {7, 2, 6, 1, 4, 9, 8};
    int array2[] = {7, 2, 6, 7, 4, 9, 8};

    // 配列を昇順にソートする
    qsort(array1, SIZE_OF_ARRAY(array1), sizeof(int), compare_int);
    qsort(array2, SIZE_OF_ARRAY(array2), sizeof(int), compare_int);

    printf("%d\n", array_is_unique(array1, SIZE_OF_ARRAY(array1)));
    printf("%d\n", array_is_unique(array2, SIZE_OF_ARRAY(array2)));
}

実行結果:

1
0

ソートされているのなら、もし値が重複する要素があれば、必ず隣り合ったところにあるはずです。よって、先頭から順番に走査しつつ、1つ後ろの要素との一致だけを確認すればいいことになります。

ここでは配列を、qsort関数を使ってソートしていますが、ソートの処理が加わったことで結局、遅くなる可能性に注意してください(配列をソートする方法については、「逆引き 配列をソートする」を参照)。


参考リンク


更新履歴

’2019/10/28 新規作成。



逆引きのトップページへ

C言語編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る