C言語で配列内の要素の最初と最後のインデックス間の最大差を求める方法

サイズNの整数配列が与えられ、その要素はランダムな順序で並んでいます。この課題では、配列内のある要素について「最初に出現するインデックス」と「最後に出現するインデックス」の差を求め、その差が最大となる値を見つけます。つまり、配列内に2回以上出現する数値の中から、インデックス間の距離が最も大きくなるものを探し出すことになります。条件を満たすペアが複数存在する場合は、その中で最大の差を答えとして返します。

入力例と出力例

入力

Arr[] = { 2,1,3,1,3,2,5,5 }

出力 − 配列内の要素の最初と最後のインデックス間の最大差 − 5

説明 − 各要素のペアとそのインデックス間の差は以下の通りです。

(2,2) Arr[0] と Arr[5] → 5-0=5 現時点での最大差は 5
(1,1) Arr[1] と Arr[3] → 3-1=2 現時点での最大差は 5
(3,3) Arr[2] と Arr[4] → 4-2=2 現時点での最大差は 5
(5,5) Arr[6] と Arr[7] → 7-6=1 現時点での最大差は 5

入力

Arr[] = { 2,2,3,4,8,3,4,4,8,7 }

出力 − 配列内の要素の最初と最後のインデックス間の最大差 − 4

説明 − 各要素のペアとそのインデックス間の差は以下の通りです。

(2,2) Arr[0] と Arr[1] ; 1-0=1; 現時点での最大差は 1
(3,3) Arr[2] と Arr[5] ; 5-2=3; 現時点での最大差は 3
(4,4,4) Arr[3],Arr[6],Arr[7] ; 7-6=1,6-3=3,7-3=4; 現時点での最大差は 4
(8,8) Arr[4] と Arr[8] ; 8-4=4; 現時点での最大差は 4

アルゴリズムの考え方

• 重複した数値をランダムな順序で含む整数配列(Arr[])を宣言します。

• 配列のサイズを格納するための変数(N)を作成します。

• 関数 maxDifference(int Arr[], int n) は、配列内の要素の最初と最後のインデックス間の最大差(maxD)を計算します。

• maxDifference() の内部では、これまでに見つかったインデックス差の最大値を保持するために変数 maxD を宣言します。

• 先頭要素(インデックス i=0)から開始し、forループで配列全体を走査します。

• 入れ子になったforループで、残りの部分(j=i+1)を末尾のインデックスまで走査します。

• Arr[i] と同じ値の要素が見つかったら、そのインデックス同士の差(j-i)を計算し、現在の maxD より大きければ maxD を更新します。

• この処理を両方のforループが終了するまで繰り返します。

• 最後に、maxD に保存された結果を返します。

コード例

#include <stdio.h>
int maxDifference(int arr[], int n){
    int maxD = 0;
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            if(arr[i] == arr[j] && (j-i) > maxD)
                maxD = j-i;
        }
    }
    return maxD;
}
int main(){
    int Arr[] = {1, 4, 1, 3, 3, 5, 4, 5, 2};
    int N = sizeof(Arr) / sizeof(Arr[0]);
    printf("Maximum difference between first and last indexes of an element in array : %d", maxDifference(Arr, N));
    return 0;
}

出力

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

Maximum difference between first and last indexes of an element in array : 5

計算量について

この手法ではすべての要素の組み合わせを比較するため、時間計算量はO(n²)となります。小規模な配列では問題ありませんが、データ量が多い場合は、各値の最初の出現位置をハッシュテーブルなどに記録しながら一度だけ配列を走査する方法(O(n))を検討すると効率的です。