C++で2つの配列の要素の和からなる集合のN番目の要素を検索する方法

この記事では、サイズmの2つのソート済み配列 arr1[] と arr2[]、および整数Nが与えられたときに、「2つの配列の要素の和から形成される集合」の中のN番目の要素を求める方法を解説します。

問題の概要

ここで扱う集合とは、arr1[i] + arr2[j](i、j < m)で表されるすべての和の値を、重複なく集めたものです。与えられたNに対して、この集合のN番目の要素の値を求めるのが課題となります。

入力例

arr1[] = {3, 1, 5} , arr2[] = {6, 2, 8} , N = 4

出力

7

説明

2つの配列の要素の和から作られる集合の要素は以下の通りです。

9 (3+6 と 1+8)、5 (3+2)、11 (3+8 と 5+6)、7 (1+6 と 5+2)、3 (1+2)、13 (5+8)

重複を除いた集合は {9, 5, 11, 7, 3, 13} となり、4番目の要素は 7 であることがわかります。

解法アプローチ

基本的な考え方はシンプルです。外側のループで arr1 の各要素を、内側のループで arr2 の各要素を走査し、すべての組み合わせについて和を計算します。計算した和を順に集合へ格納し、すでに存在する値は追加しないことで重複を排除します。すべての和を格納し終えたら、N番目の要素を取り出して返します。

アルゴリズムの手順

1. 結果を格納するための空の集合を用意します。
2. 二重ループで arr1[i] + arr2[j] のすべての組み合わせの和を計算します。
3. その和がまだ集合に存在しない場合のみ、集合に追加します。
4. すべての和を格納した後、集合のN番目の要素を返します。

C++での実装例

#include <iostream>
#include <vector>
using namespace std;

// 2つの配列の和からなる集合のN番目の要素を求める関数
int findNthItem(int arr1[], int arr2[], int m, int N) {
    vector<int> resultSet;
    // すべての組み合わせの和を計算
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            int sum = arr1[i] + arr2[j];
            // 重複チェック
            bool exists = false;
            for (int k = 0; k < (int)resultSet.size(); k++) {
                if (resultSet[k] == sum) {
                    exists = true;
                    break;
                }
            }
            if (!exists)
                resultSet.push_back(sum);
        }
    }
    // N番目の要素を返す
    if (N > 0 && N <= (int)resultSet.size())
        return resultSet[N - 1];
    return -1;
}

int main() {
    int arr1[] = {3, 1, 5};
    int arr2[] = {6, 2, 8};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int N = 4;
    cout << N << "番目の要素は " << findNthItem(arr1, arr2, m, N) << endl;
    return 0;
}

出力

4番目の要素は 7

計算量について

この解法では、m×m通りの組み合わせの和を計算し、さらに重複チェックを行うため、時間計算量は O(m²×k)(kは集合の要素数、最悪ケースでO(m³))となります。空間計算量は O(k) です。

補足：std::set を使った別解

C++の std::set を利用すれば、重複の管理をライブラリ側に任せることができ、コードをより簡潔にできます。ただし、std::set は要素を自動的に昇順ソートするため、N番目の要素は「挿入順」ではなく「昇順」で判定される点に注意してください。