C++で配列内の「x < y」となるペア(x, y)の個数を数える方法

問題の概要

整数型の配列が与えられます。この配列の値を組み合わせて作成できるペア(x, y)のうち、x の値が y より小さいという条件を満たすペアの総数を求めるのが本記事の課題です。

入力： int arr[] = { 2, 4, 3, 1 }

出力： x < y となる配列内のペア(x, y)の個数 ― 6

説明

入力配列 { 2, 4, 3, 1 } から作れるすべての順序付きペアを検証すると、結果は次のようになります。

この表から、条件を満たすペアは全部で 6 個であることが確認できます。

プログラムで使用するアプローチ

• ペアを作る元となる整数要素の配列を受け取ります。
• 配列のサイズを計算し、後続の処理のためにデータを関数へ渡します。
• x < y を満たすペアの数を格納するための一時変数 count を用意します。
• i を 0 から配列サイズまで動かす外側の FOR ループを開始します。
• そのループの中で、j を 0 から配列サイズまで動かす内側の FOR ループを開始します。
• 内側のループの中で、arr[i] < arr[j] が真であれば count を 1 増やします。
• すべての組み合わせを調べ終えたら count を返します。
• 結果を出力します。

サンプルコード（C++）

#include <iostream>
using namespace std;
int X_Less_Y(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        for (int j = 0; j < size; j++){
            if (arr[i] < arr[j]){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = { 2, 4, 3, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"x < y となる配列内のペア(x, y)の個数: "<<X_Less_Y(arr, size);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

x < y となる配列内のペア(x, y)の個数: 6

計算量と効率化のヒント

この実装では二重ループですべてのペアを調べるため、時間計算量は O(n²) となります。配列の要素数が増えると処理時間が急激に伸びる点には注意が必要です。

より効率化したい場合は、配列をあらかじめソートしておき、二分探索（std::lower_bound など）を使って「自分より大きい要素の個数」を求める方法が有効です。この場合、計算量を O(n log n) まで抑えることができます。