C++で2つの配列を交互にマージして第3の配列を作成する方法

問題概要

2つの配列が与えられたとき、それらを組み合わせて、第1の配列と第2の配列の要素が交互に並んだ新しい配列（結果配列）を作成します。片方の配列に余分な要素がある場合は、その残りの要素を結果配列の末尾に追加します。

arr1[] = {10, 20, 30, 40}
arr2[] = {-10, -20, -30, -40}
result[] = {10, -10, 20, -20, 30, -30, 40, -40}

この例では、両方の配列の長さが同じため、要素が完全に交互に配置されています。もし arr1 の方が長ければ、余った要素は result の最後にそのまま追加されます。

アルゴリズム

1. 両方の配列を同時に走査し、1つずつ要素を結果配列に格納していきます（arr1 の要素、次に arr2 の要素という順序）。
2. どちらか一方の配列の要素を使い切ったら、もう一方の配列の残りの要素をすべて結果配列に追加します。

計算量

このアルゴリズムの時間計算量は O(n1 + n2) です。ここで n1 と n2 はそれぞれの配列の要素数です。各要素を一度だけ処理するため、非常に効率的です。

実装例

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

void alternateMergedArray(int *arr1, int n1, int *arr2, int n2, int *result){
    int i, j, k;
    i = 0;
    j = 0;
    k = 0;
    // 両方の配列から交互に要素を取り出す
    while (i < n1 && j < n2) {
        result[k] = arr1[i];
        ++k;
        ++i;
        result[k] = arr2[j];
        ++k;
        ++j;
    }
    // arr1 に残りがあれば末尾に追加
    while (i < n1) {
        result[k] = arr1[i];
        ++k;
        ++i;
    }
    // arr2 に残りがあれば末尾に追加
    while (j < n2) {
        result[k] = arr2[j];
        ++k;
        ++j;
    }
}

void displayArray(int *arr, int n){
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main(){
    int arr1[] = {10, 20, 30, 40};
    int arr2[] = {-10, -20, -30, -40};
    int result[SIZE(arr1) + SIZE(arr2)];
    cout << "First array: " << endl;
    displayArray(arr1, SIZE(arr1));
    cout << "Second array: " << endl;
    displayArray(arr2, SIZE(arr2));
    cout << "Result array: " << endl;
    alternateMergedArray(arr1, SIZE(arr1), arr2, SIZE(arr2), result);
    displayArray(result, SIZE(result));
    return 0;
}

コードの解説

• alternateMergedArray 関数：最初の while ループでは、両方の配列にまだ要素が残っている間、arr1 と arr2 から交互に要素を取り出して result に格納します。
• 2つ目と3つ目の while ループは、どちらか一方の配列が先に使い切られた場合に対応するものです。残った側の要素を順番に result へコピーします。
• SIZE マクロ：配列全体のバイトサイズを要素1つ分のサイズで割ることで、配列の要素数を求めています。

出力結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

First array:
10 20 30 40
Second array:
-10 -20 -30 -40
Result array:
10 -10 20 -20 30 -30 40 -40

このように、2つの配列の要素が正しく交互にマージされていることが確認できます。配列の長さが異なる場合でも、短い方の配列を使い切った後、長い方の残りの要素が自動的に末尾へ追加されるため、柔軟に対応できます。