Skip to main content
追記
ソース リンク
OOPer
  • 1.9万
  • 2
  • 16
  • 33

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


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

ソース リンク
OOPer
  • 1.9万
  • 2
  • 16
  • 33

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

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

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

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

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