

C言語についての質問です。  
二つの配列A,Bがありそれぞれに整数が格納されていて、配列の中の数は昇順にソートされていて、配列Aの中には重複する数がなく、それは配列Bについても一緒である。  
ただし、配列AとBのサイズは同じとは限らない。

それを踏まえて配列AとBの中には重複する数があり、その重複して含まれる数を出力するプログラムを教えてください


CC BY-SA 4.0
2018-10-09T05:45:15.167
49089
2018-10-11T05:50:53.707
2018-10-09T07:26:20.667
3054
30429
question
c アルゴリズム array
自身の要素に重複が無い昇順の配列同士で、共通している要素を求めたい


２つの配列は、いずれも要素に重複が無く、要素はソートされている訳ですから、配列A用のインデックスの変数と、配列B用のインデックスの変数を用意（初期値は0)しておいて、

配列Aで注目している要素と、配列Bで注目している要素を比較して、  
一致していたら、  
重複する数なので、重複した数の個数を＋１する。両方の配列のインデックス(注目する要素の位置）を+1する。  
配列Aの要素のほうが大きかったら、  
配列Bのインデックス(注目する要素の位置）を+1する（配列Bの次に大きい数で比較を試みる）  
配列Bの要素のほうが大きかったら、  
配列Aのインデックス(注目する要素の位置）を+1する（配列Aの次に大きい数で比較を試みる）

というのをループで回せば良いのではないかと思います。  
（どちらかの配列のインデックスが、最大値を超えたところでループを終わりにしてください）


CC BY-SA 4.0
2018-10-09T08:05:59.867
49094
2018-10-09T08:05:59.867
217
49089
answer


簡単にやるには単純な二重ループを書けば良いのですが、双方の配列が昇順にソートされていることを利用して内側のループをうまく制御するとO(N)の計算量ですみます。Nの値が1000000のオーダーになると単純二重ループとは全然差が出てきます。

[code]

    #include <stdio.h>
    #include <stdlib.h>
    
    #define N 10
    
    //入力データ
    int arr1[N];
    int arr2[N];
    //結果
    int result[N];
    int resultCount = 0;
    
    int main(int argc, const char * argv[]) {
    
        //入力データを乱数で作成
        int num = 0;
        for( int i = 0; i < N; ++i ) {
            num += rand() % 3 + 1;
            arr1[i] = num;
        }
        num = 0;
        for( int i = 0; i < N; ++i ) {
            num += rand() % 3 + 1;
            arr2[i] = num;
        }
    
        //重複部分を求める部分本体
        int j = 0;
        //`arr1`側は最初から順番に読み出す
        for( int i = 0; i < N; ++i ) {
            int n1 = arr1[i];
            //`arr2`側の値が`n1`に並ぶか追い越すまで`arr2`の読み出し位置を進める
            while( j < N && n1 > arr2[j] ) {
                ++j;
            }
            //並んだ(重複)のであれば、結果に加える
            if( j < N && n1 == arr2[j] ) {
                result[resultCount++] = n1;
                j += 1;
            }
        }
    
        //入力データと結果出力
        for( int i = 0; i < N; ++i ) {
            if( i > 0 ) {
                printf(",");
            }
            printf("%d", arr1[i]);
        }
        printf("\n");
    
        for( int i = 0; i < N; ++i ) {
            if( i > 0 ) {
                printf(",");
            }
            printf("%d", arr2[i]);
        }
        printf("\n");
    
        for( int i = 0; i < resultCount; ++i ) {
            if( i > 0 ) {
                printf(",");
            }
            printf("%d", result[i]);
        }
        printf("\n");
        printf("%d\n", resultCount);
    
        return 0;
    }
    
[/code]

入力データの作成と結果の出力部分が長くなってしまいましたが、`arr1`を舐めるための`i`と`arr2`を舐めるための`j`を別々に制御して、同じ要素を舐めないように(でも重複要素は見逃さないように)ループしているだけです。内側のループにも`for`文を使っても良かったんですが、慣れてないと???なコードに見えそうなので`while`にしておきました。

動作がよく理解できない場合は、`N`の値を小さめにしてステップ実行できる環境で`i`, `j`の変化を追って見てください。

比較対象にする単純二重ループの方は、ぜひご自身で完成させて、両者の速度の違いを比較して見てください。

* * *

(追記)  
本質的に Fumu 7 さんや、nekketsuuu さんの「より効率的な方法」と同じ内容です。でも、nekketsuuu
さんのコードの方がわかりやすそうですね。


CC BY-SA 4.0
2018-10-09T08:07:06.527
49095
2018-10-09T08:15:42.737
2018-10-09T08:15:42.737
13972
13972
49089
answer


### 無駄のある方法

まず、愚直に解くのであれば、配列 a の要素が配列 b に含まれるかどうか1つずつ調べれば良いです。たとえば以下の例で考えてみます。

[code]

    int a[] = {1, 5, 9};
    int b[] = {2, 3, 5, 7, 11};
    
[/code]

この例であれば、まず `a[0]` である `1` が `b` に含まれるか調べます。含まれません。そのあと `a[1]` である `5`
が含まれるか調べます。含まれます。最後に `a[2]` である `9` が含まれるか調べます。含まれません。含まれた回数を数えれば、`a` と `b`
が重複して含んでいる要素の数が分かります。

しかしこの方法には無駄があります。この方法は `a` の要素 1 つごとに `b` の要素をイチから探索しますが、2
つの配列がソートされているという仮定を使うともっと効率よく調べることができるのです。

### より効率的な方法

2 つの配列は共にソートされているので、2 つの配列を最初の要素から同時に調べることができます。具体的には次のようなアルゴリズムです。

[code]

    1. count = 0 と初期化する
    2. i = 0, j = 0 と初期化する
    3. a[i] か b[j] のどちらかが配列末尾を通り越すまで以下を繰り返す:
        // 見ている場所が等しければ、count を 1 増やして次にいく
        2-1. もし a[i] == b[j] なら:
            2-1-1. count++
            2-1-2. i++, j++  // それぞれの配列の中では要素が重複していないのでこれで良い
        // どちらかが真に小さければ、小さい方だけ次に進める
        2-2. そうでなくて、もし a[i] < b[j] なら:
            2-2-1. i++
        2-3. そうでないなら (つまり a[i] > b[j] なら):
            2-3-1. j++
    4. count を出力する
    
[/code]

このアルゴリズムは配列の要素の小さい方から順番に比較しています。`i` と `j`
がそれぞれの配列を「見ている場所」であり、見ている場所を徐々に後ろに動かしています。2
つの配列はソートされているので、既に通り越した要素は今見ている場所の要素とは絶対に等しくないというのがキーポイントです。

先ほどと同じ例で、このアルゴリズムの動作を確かめてみます。

[code]

    int a[] = {1, 5, 9};
    int b[] = {2, 3, 5, 7, 11};
    
[/code]

[code]

     i | j | a[i] | b[j] |
    ----------------------------------------------
     0 | 0 |    1 |    2 | a[i] の方が小さいので i++
     1 | 0 |    5 |    2 | b[j] の方が小さいので j++
     1 | 1 |    5 |    3 | b[j] の方が小さいので j++
     1 | 2 |    5 |    5 | a[i] == b[j]！
     2 | 3 |    9 |    7 | b[j] の方が小さいので j++
     2 | 4 |    9 |   11 | a[i] の方が小さいので i++ → a の終端に達したので終了
    
[/code]

このアルゴリズムを実際に実装したものは [Wandbox
に置いておきます](https://wandbox.org/permlink/n1FkcG5a4eyQbQX1)。


CC BY-SA 4.0
2018-10-09T08:10:22.247
49096
2018-10-09T08:16:44.890
2018-10-09T08:16:44.890
19110
19110
49089
answer


配列の要素の傾向によっては二分探索の使用も考慮の余地があると思いますので、例を出しておきます。

基本的には既にあるループを用いた回答（[1](https://ja.stackoverflow.com/a/49096/3054)、[2](https://ja.stackoverflow.com/a/49094/3054)、[3](https://ja.stackoverflow.com/a/49095/3054)）と同じです。これらの回答にはAかBのインデックスを
`+1` している部分があるかと思いますが、これを関数 `search_greater_or_eq` で一気に進めることで高速化を試みています。

二分探索の使用で速くなるのは、大ざっぱに言うと配列Aと配列Bの要素の分布が大きく異る場合で、要素の範囲があまり重なっていなかったり、一方の要素数が他方に比べ極端に少なく疎であるようなケースです。似たような分布（例えば、ある範囲に含まれる数の偶数をAに、奇数をBに含めた場合）では逆に遅くなります。

[code]

    #include <stdio.h>
    #include <stdlib.h>
    
    // 二分探索で n 以上の要素の中で最小である要素のインデックスを返す
    // 注意！ 見付からなかった場合 **範囲外のインデックス (length) を返す**
    // 呼び出し元でチェックすること
    size_t search_greater_or_eq(int n, int arr[], size_t start, size_t length) {
        size_t low = start;
        size_t high = length - 1;
        size_t greater = length;
        while (low <= high) {
            size_t mid = (low + high) / 2;
            if (arr[mid] > n) {
                high = mid - 1;
                greater = mid;
            } else if (arr[mid] < n) {
                low = mid + 1;
            } else { // arr[mid] == n
                return mid;
            }
        }
        return greater;
    }
    
    
    int count_duplicate(int a[], size_t a_length, int b[], size_t b_length) {
        int count = 0;
        size_t a_pos = 0;
        size_t b_pos = 0;
    
        while (a_pos < a_length && b_pos < b_length) {
            if (a[a_pos] == b[b_pos]) {
                //printf("%d\n", a[a_pos]);
                count++;
                a_pos++;
                b_pos++;
            } else if (a[a_pos] > b[b_pos]) {
                b_pos = search_greater_or_eq(a[a_pos], b, b_pos, b_length);
            } else {
                a_pos = search_greater_or_eq(b[b_pos], a, a_pos, a_length);
            }
        }
    
        return count;
    }
    
    
    int main() {
        size_t A_length = 100000000;
        int *A = malloc(sizeof(int) * A_length);
        for (int i=0; i<A_length; i++) {
            A[i] = i + 1;
        }
        size_t B_length = 6;
        int B[] = {0, 1, A_length/4, A_length/2, A_length, A_length+1};
    
        printf("A: %d 〜 %d\n", A[0], A[A_length -1]);
        printf("B: %d 〜 %d\n", B[0], B[B_length -1]);
        printf("重複合計: %d\n", count_duplicate(A, A_length, B, B_length));
    
        free(A);
    }
    
[/code]

出力:

[code]

    A: 1 〜 100000000
    B: 0 〜 100000001
    重複合計: 4
    
[/code]

`search_greater_or_eq`
を二分探索でなく、順番に見ていくものにすれば、他の回答で説明されているアルゴリズムとほぼ同じになるはずです。やはり、この場合も配列の分布が大きく異ると、`search_greater_or_eq`
の中のコンパクトなループを回る割合が増えるので、多少は速くなることが期待できますが、C言語の場合はほぼ影響が無いでしょう。

[code]

    // 線形探索バージョン
    size_t search_greater_or_eq(int n, int arr[], size_t start, size_t length) {
        size_t i;
        for (i=start; i < length; i++) {
            if (arr[i] >= n) {
                return i;
            }
        }
        return length;
    }
    
[/code]


CC BY-SA 4.0
2018-10-10T16:40:24.907
49156
2018-10-11T05:50:53.707
2018-10-11T05:50:53.707
3054
3054
49089
answer


出現する要素の範囲がある程度決まってて、メモリもある程度潤沢に使えるのであれば、バケツを使う方法もあります。  
最大値と最小値さえわかれば、両配列がソートされていなくとも重複がわかるのも利点です。

[code]

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MIN(a,b) ((a) < (b) ? (a) : (b))
    #define MAX(a, b) ((a) > (b) ? (a) : (b))
    
    int main()
    {
        int i = 0;
        int cnt = 0;
    
        int a[] = {1, 5, 9, 11, 12, 15, 16, 17,18};
        int b[] = { 3, 5, 7, 11, 15, 18};
    
        int a_len = sizeof(a) / sizeof(int);//配列aの要素数
        int b_len = sizeof(b) / sizeof(int);//配列bの要素数
    
        int min = MIN(a[0], b[0]);//最小値
        int max = MAX(a[a_len - 1], b[b_len - 1]);//最大値
    
        int *bucket = calloc(max - min + 1, sizeof(int));//バケツ用意
    
        for(i = 0; i < a_len; i++)
        {
            bucket[a[i] - min]++;
        }
    
        for(i = 0; i < b_len; i++)
        {
            bucket[b[i] - min]++;
        }
    
        printf("重複しているのは、\n");
        for(i = min; i <= max; i++)
        {
            if(bucket[i - min] == 2)
            {
                printf("%d\n", i);
                cnt++;
            }
        }
        printf("の%d件です。\n", cnt);
    
    
        free(bucket);//メモリ開放
    
        return 0;
    }
    
[/code]

以下のサイトで動作確認済みです。  
<http://www.tutorialspoint.com/compile_c_online.php>


CC BY-SA 4.0
2018-10-11T03:23:55.237
49173
2018-10-11T03:23:55.237
17014
49089
answer