簡単にやるには単純な二重ループを書けば良いのですが、双方の配列が昇順にソートされていることを利用して内側のループをうまく制御すると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
を舐めるためのi
とarr2
を舐めるためのj
を別々に制御して、同じ要素を舐めないように(でも重複要素は見逃さないように)ループしているだけです。内側のループにもfor
文を使っても良かったんですが、慣れてないと???なコードに見えそうなのでwhile
にしておきました。
動作がよく理解できない場合は、N
の値を小さめにしてステップ実行できる環境でi
, j
の変化を追って見てください。
比較対象にする単純二重ループの方は、ぜひご自身で完成させて、両者の速度の違いを比較して見てください。