C++で最大差を持つペアの選び方を数える方法

問題の概要

数値の配列 Arr[] が与えられます。目的は、考えられるすべてのペアの中で「最大の差」と等しい差を持つペアが何通りあるかを数えることです。条件は i != j であり、arr[x] − arr[y] が取り得る最大値になるような組み合わせを探します。

解き方はシンプルです。まず最大差(maxdiff)を求め、その後で差が maxdiff と一致するすべてのペアをカウントします。

入出力例1

入力: arr[] = { 1, 2, 3, 2, 4, 1, 5 }

出力: 最大差を持つペアの選び方の数 ― 2

説明:

配列の最小値は1、最大値は5なので、最大差 = 5 − 1 = 4
ペア1 [ 1,2,3,2,4,1,5 ] → (1, 5) 差 = 4
ペア2 [ 1,2,3,2,4,1,5 ] → (1, 5) 差 = 4
最大差を持つペアの数 = 2

入出力例2

入力: arr[] = { 2, 4, 2, 4 }

出力: 最大差を持つペアの選び方の数 ― 4

説明:

配列の最小値は2、最大値は4なので、最大差 = 4 − 2 = 2
ペア1 [ 2,4,2,4 ] → (2, 4) 差 = 2
ペア2 [ 2,4,2,4 ] → (2, 4) 差 = 2
ペア3 [ 2,4,2,4 ] → (4, 2) 差 = 2
ペア4 [ 2,4,2,4 ] → (2, 4) 差 = 2
最大差を持つペアの数 = 4

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

• ランダムな整数で初期化された整数型配列 Arr[] を用意します。
• 配列 Arr[] の長さを格納する変数 N を用意します。
• 関数 countPairs(int arr[], int n) は、配列とその長さを引数として受け取り、最大差と等しい差を持つペアの選び方の数を返します。
• 選び方の数を数えるため、初期値 0 の変数 count を用意します。
• 各ペアの差を格納する変数 diff を用意します。
• 全ペアの中で最大の差を格納する変数 maxdiff を用意します。
• 配列から最大値と最小値を求め、それぞれ maxx と mini に保存します。
• すると maxdiff は maxx − mini として計算できます。
• ペアを構成する要素ごとに、2つのforループで配列を走査します。
• 外側のループは 0 ≤ i < n−1、内側のループは i < j < n となります。
• diff = arr[i] − arr[j] と arr[j] − arr[i] をそれぞれ別のペアとして計算し、diff == maxdiff であれば、そのペアは最大差を持つため count をインクリメントします。
• すべてのループが終了した時点で、count には条件を満たすペアの総数が格納されています。
• 結果として count を返します。

サンプルコード(C++)

#include <bits/stdc++.h>
using namespace std;
int countWays(int arr[],int n){
    int count = 0;
    int diff;
    int maxdiff=0; // 初期化
    int mini,maxx;
    mini=maxx=arr[0];
    for (int i = 0; i < n; i++) // 最小値と最大値を求める{
        if(arr[i]<mini)
            {mini=arr[i];}
        if(arr[i]>maxx)
            { maxx=arr[i]; }
    }
    maxdiff=maxx-mini; // これが最大差
    //cout<<maxx<<" "<<mini;
    for (int i = 0; i < n-1; i++){
        for (int j = i+1; j < n; j++){
            diff=arr[i]-arr[j]; // ペア1
            if ( diff==maxdiff ){
                count++;
                //cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; // 表示用
            }
            diff=arr[j]-arr[i]; // ペア2
            if ( diff==maxdiff ){
                count++;
                //cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; // 表示用
            }
        }
    }
    return count;
}
int main(){
    int Arr[]={ 3, 2, 1, 1, 3 };
    int N=5; // 配列の長さ
    cout <<endl<< "No. of ways of choosing pair with maximum difference : "<<countWays(Arr,N);
    return 0;
}

出力

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

No. of ways of choosing pair with maximum difference : 4

計算量と最適化のポイント

この実装は二重ループを使用しているため、時間計算量は O(n²) です。しかし、最大差は必ず「最大値 − 最小値」によって達成されるため、より効率的な方法があります。配列内に最小値が出現する回数を cntMin、最大値が出現する回数を cntMax と数えれば、答えは cntMin × cntMax として O(n) で求められます。先ほどの例 {3, 2, 1, 1, 3} では、最小値 1 が2回、最大値 3 が2回出現するため 2 × 2 = 4 となり、実際の結果と一致します。なお、配列のすべての要素が同じ値の場合は最小値と最大値が等しくなるため、すべてのペアが条件を満たす点に注意してください。