C++で配列内の正と負の整数ペアをすべて出力する効率的なアルゴリズム

問題の概要

この問題では、重複しない整数からなる配列が与えられます。ここで求められるのは、配列内に存在する「正の整数」と「負の整数」のペア(絶対値が等しい組み合わせ)をすべて出力することです。

まず、具体例を見ながら問題を理解しましょう。

入力: array = {1, 4, 7, -1, 2, 5, -7}
出力: (-1, 1) (-7, 7)

単純な解法とその課題

最も簡単なアプローチは、二重ループを使って正負のペアを総当たりで探す方法です。しかし、この解法はコードが複雑になりやすく、時間計算量もO(n²)(nは配列のサイズ)となるため、配列が大きくなるほど実用的ではなくなります。

効率的な解法：ソートと二分探索の活用

そこで、より効率的なアプローチを採用します。手順は以下の通りです。

1. まず配列を昇順にソートします。
2. ソート済み配列において、各負の整数に対して、対応する正の整数(絶対値が同じ値)を二分探索(binary search)で検索します。
3. 見つかったペアを出力します。

この方法なら時間計算量はO(n log n)に抑えられ、二重ループ方式のO(n²)と比べて大幅に高速化できます。

C++での実装例

それでは、この手法をC++で実装したコードを見てみましょう。

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

void positiveNegativePair(int arr[], int n);

int main(){
    int arr[] = { 1, 4, 6, 3, -1, -2, 5, -6, -5, 8 };
    int n = 10;
    cout << "Positive Negative pairs in the array are :\n";
    positiveNegativePair(arr, n);
    return 0;
}

void positiveNegativePair(int arr[], int n){
    bool pair_exists = false;
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        if (arr[i] < 0) {
            if (binary_search(arr, arr + n, -arr[i])) {
                cout << arr[i] << ", " << -arr[i] << "\t";
                pair_exists = true;
            }
        }
        else
            break;
    }
    if (!pair_exists)
        cout << "No positive-negative pairs exist in the array";
}

出力結果

配列内の正負のペアは以下の通りです。

-6, 6   -5, 5   -1, 1

コードのポイント解説

• sort()関数： 配列を昇順に並べ替えることで、負の数が先頭側に集まります。
• ループとbreak文： 負の整数だけを走査し、最初の正の数に到達した時点でループを抜けるため、無駄な比較が発生しません。
• binary_search()関数： 標準ライブラリの二分探索により、各負の整数に対応する正の整数が存在するかどうかをO(log n)で効率よく判定します。
• pair_existsフラグ： ペアが一件も見つからなかった場合に、その旨のメッセージを表示するために使用されます。

計算量

時間計算量:O(n log n)(ソートおよび各要素の二分探索)
空間計算量:O(1)(追加のメモリ不要)