C++で別の配列を使って配列の要素を最大化する方法

C++では、2つの配列を組み合わせて「大きい要素だけを持つ配列」を作り出すことができます。本記事では、サイズnの2つの配列が与えられたとき、両方の配列からn個の最大かつ重複しない要素を抜き出し、第2配列を優先しながら元の順序を保って第1配列を書き換えるアルゴリズムを、サンプルコードと実行結果あわせて解説します。

問題の概要

サイズnの2つの配列が与えられます。第2配列の要素を使って第1配列を最大化します。このとき、新しく作られる配列は次の条件を満たす必要があります。

• 両方の配列に含まれる要素の中から、大きい方からn個を選ぶ
• 選んだ要素は重複してはならない(すべて一意であること)
• 第2配列の要素を優先する(同じ値が両方にある場合は第2配列側を採用)
• 出力における要素の並び順は、入力配列での出現順序を維持する

たとえば、arr1[] = {12, 15, 10}、arr2[] = {16, 17, 5} の場合、順序を保ちながら選んだ最大要素は {16, 17, 15} となります。

アルゴリズム

1. サイズ 2×n の一時配列を作成する。
2. arr1 と arr2 のすべての要素を一時配列にコピーし、降順にソートする。
3. 入力配列での出現順序を保持するため、ハッシュテーブル(unordered_set)を使用する。
4. ソート済みの一時配列を先頭から走査し、大きい方から順に「n個の一意な要素」をハッシュテーブルに登録する。
5. まず第2配列を走査し、ハッシュテーブルに存在する要素を一時配列の先頭から詰めて格納する。
6. 続いて第1配列を走査し、同様にハッシュテーブルに存在する要素を格納する。
7. この手順により、両配列から選ばれた「n個の最大かつ一意な要素」が出現順序どおりに一時配列へ格納される。

C++による実装例

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

// 配列の内容を出力する関数
void printArray(int *arr, int n) {
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 降順ソート用の比較関数
bool compare(int a, int b) {
    return a > b;
}

// 第1配列を最大化する関数
void getMaxElements(int *arr1, int *arr2, int n) {
    vector<int> temp(2 * n);
    int k = 0;

    // 両方の配列の要素を一時配列にまとめる
    for (int i = 0; i < n; ++i) {
        temp[k++] = arr1[i];
    }
    for (int i = 0; i < n; ++i) {
        temp[k++] = arr2[i];
    }

    // 降順にソート
    sort(temp.begin(), temp.end(), compare);

    // 大きい方からn個の一意な要素をハッシュセットに登録
    unordered_set<int> selected;
    int i = 0;
    while ((int)selected.size() != n) {
        if (selected.find(temp[i]) == selected.end()) {
            selected.insert(temp[i]);
        }
        ++i;
    }

    k = 0;
    // まず第2配列を優先して格納
    for (int i = 0; i < n; ++i) {
        if (selected.find(arr2[i]) != selected.end()) {
            temp[k++] = arr2[i];
            selected.erase(arr2[i]);
        }
    }
    // 続いて第1配列の残りの要素を格納
    for (int i = 0; i < n; ++i) {
        if (selected.find(arr1[i]) != selected.end()) {
            temp[k++] = arr1[i];
            selected.erase(arr1[i]);
        }
    }

    // 結果を第1配列へ書き戻す
    for (int i = 0; i < n; ++i) {
        arr1[i] = temp[i];
    }
}

int main() {
    int arr1[] = {12, 15, 10};
    int arr2[] = {16, 17, 5};
    int n = sizeof(arr1) / sizeof(arr1[0]);

    cout << "First array:\n";
    printArray(arr1, n);
    cout << "Second array:\n";
    printArray(arr2, n);

    getMaxElements(arr1, arr2, n);

    cout << "Maximum array:\n";
    printArray(arr1, n);

    return 0;
}

実行結果

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

First array:
12 15 10
Second array:
16 17 5
Maximum array:
16 17 15

コードのポイント

1. ハッシュセットによる重複排除と高速な存在判定

unordered_set を使うことで、ある値がすでに選択済みかどうかを平均 O(1) で判定できます。降順ソート済みの一時配列を先頭から走査し、未登録の値だけをセットに追加していくため、重複した値は自然に除外されます。

2. 第2配列を優先する仕組み

ハッシュテーブルへの登録後、まず第2配列を走査して該当要素を確定させ、使用した要素は erase() でセットから削除します。その後で第1配列を走査するため、同じ値が両方の配列に存在しても、必ず第2配列側の要素が先に採用されます。

3. 順序が崩れない理由

最終的な並び順はソート結果ではなく「入力配列の走査順」によって決まります。第2配列→第1配列の順に走査して一時配列へ詰めていくため、出力は入力での出現順序をそのまま保ちます。

計算量

• 時間計算量:ソートが支配的なので O(n log n)
• 空間計算量:補助配列とハッシュセットの分 O(n)