質問: C言語についての質問です。 二つの配列A,Bがありそれぞれに整数が格納されていて、配列の中の数は昇順にソートされていて、配列Aの中には重複する数がなく、それは配列Bについても一緒である。 ただし、配列AとBのサイズは同じとは限らない。 それを踏まえて配列AとBの中には重複する数があり、その重複して含まれる数を出力するプログラムを教えてください🙏
回答: 簡単にやるには単純な二重ループを書けば良いのですが、双方の配列が昇順にソートされていることを利用して内側のループをうまく制御するとO(N)の計算量ですみます。Nの値が1000000のオーダーになると単純二重ループとは全然差が出てきます。 ``` #include #include #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`の変化を追って見てください。 比較対象にする単純二重ループの方は、ぜひご自身で完成させて、両者の速度の違いを比較して見てください。 (追記) 本質的に Fumu 7 さんや、nekketsuuu さんの「より効率的な方法」と同じ内容です。でも、nekketsuuu さんのコードの方がわかりやすそうですね。