C++で元の順序を保ちながら2つの配列から最大要素のみで構成される配列を作成する方法

問題文

同じサイズを持つ2つの配列 A[] と B[] が与えられています。この課題では、同じサイズの第3の配列を作成します。結果の配列には、両方の配列から合計 n 個の最大要素が含まれる必要があります。まず A[] から選ばれた要素を先頭に配置し、その後に B[] から選ばれた要素を続けます。重要なのは、選ばれた要素が元の配列内での登場順序を維持しなければならないという点です。また、両方の配列に共通する要素が存在する場合は、結果配列には1つだけ含め、優先順位は A[] の側に与えます。

具体例

入力配列が次の通りだったとします。

arr1[] = {9, 17, 2, 25, 6}
arr2[] = {17, 4, 8, 10, 1}

この場合、最終的に得られる配列は次のようになります。

{9, 17, 25, 8, 10}

ここで注目すべきは、要素 17 が両方の配列に共通して現れている点です。優先順位のルールにより、arr1 側の要素が採用されています。

アルゴリズム

• 両方の配列のコピーを作成し、それぞれ降順にソートします。
• ハッシュマップを利用して、両方の配列から重複のない n 個の最大要素を選び出します。このとき arr1[] を優先します。
• 結果配列を空の状態で初期化します。
• arr1[] を先頭から走査し、ハッシュマップに存在する要素だけを結果配列へコピーします。この操作によって、要素の元の順序が保たれます。
• 同様の手順を arr2[] に対しても繰り返します。ただし今回は、arr1[] にすでに存在しない要素のみを対象とします。

計算量について

ソート処理に O(n log n)、その後の走査とハッシュ参照には O(n) の時間がかかるため、全体の時間計算量は O(n log n) となります。空間計算量もコピーとハッシュマップの分だけ O(n) 必要です。

C++による実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void printArray(vector<int> &arr, int n) {
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void getMaxArray(int *arr1, int *arr2, int n) {
    // 両方の配列のコピーを作成し、降順にソート
    vector<int> temp1(arr1, arr1 + n);
    vector<int> temp2(arr2, arr2 + n);
    sort(temp1.begin(), temp1.end(), greater<int>());
    sort(temp2.begin(), temp2.end(), greater<int>());

    // 最大 n 個の要素を選択するためのハッシュマップ
    unordered_map<int, int> m;
    int i = 0, j = 0;
    while (m.size() < n) {
        if (temp1[i] >= temp2[j]) {
            m[temp1[i]]++;
            ++i;
        } else {
            m[temp2[j]]++;
            ++j;
        }
    }

    // 元の順序を維持したまま結果を構築
    vector<int> result;
    for (int i = 0; i < n; ++i) {
        if (m.find(arr1[i]) != m.end()) {
            result.push_back(arr1[i]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (m.find(arr2[i]) != m.end() && m[arr2[i]] == 1) {
            result.push_back(arr2[i]);
        }
    }

    cout << "Final array:\n";
    printArray(result, n);
}

int main() {
    int arr1[] = {9, 17, 2, 25, 6};
    int arr2[] = {17, 4, 8, 10, 1};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    getMaxArray(arr1, arr2, n);
    return 0;
}

実行結果

Final array:
9 17 25 8 10

まとめ

この手法のポイントは、「どの要素を選ぶか」と「どの順序で並べるか」を分離して考えることです。降順ソート済みのコピー配列を使えば最大値の選択を効率的に行え、その後で元の配列を再度走査することで自然に元の順序が再現されます。共通要素の扱いもハッシュマップで管理すれば、arr1 を優先するルールを簡単に実装できます。