【C言語】配列内の同じ要素の2つの出現位置間の最大距離を求める方法

問題の概要

整数型の配列が与えられ、その中には同じ要素が複数回出現することがあります。本記事の課題は、配列内で同じ要素が出現する任意の2つのインデックス間の最大距離を求めることです。

基本的な考え方はシンプルです。配列を左から順に各要素を取り上げ、同じ数値が最後に出現するインデックスを探します。そして2つのインデックスの差を計算し、これまでに見つかった最大値より大きければ、その値を結果として保持します。

入力例1

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

出力 − 同じ要素の2つの出現位置間の最大距離：4

説明 − 繰り返し現れる数値とそれぞれのインデックスは以下の通りです。

1. 1 … 最初のインデックス 0、最後のインデックス 3、距離 = 3 - 0 - 1 = 2
2. 2 … 最初のインデックス 1、最後のインデックス 6、距離 = 6 - 1 - 1 = 4
3. 5 … 最初のインデックス 7、最後のインデックス 9、距離 = 9 - 7 - 1 = 1

同じ要素の2つの出現位置間の最大距離：4

入力例2

Arr[] = { 10, 20, 1, 10, 10, 21, 12, 0 }

出力 − 同じ要素の2つの出現位置間の最大距離：3

説明 − 繰り返し現れる数値とそれぞれのインデックスは以下の通りです。

1. 10 … 最初のインデックス 0、最後のインデックス 4、距離 = 4 - 0 - 1 = 3

同じ要素の2つの出現位置間の最大距離：3

注意： 入力配列に重複する要素がひとつも存在しない場合は、-1 を返します。

プログラムのアプローチ

以下の手順で最大距離を求めます。

• 重複した数値を含む整数配列 Arr[] を受け取ります。
• 関数 maxDistance(int arr[], int n) が、同じ要素の2つの出現位置間の最大距離を計算します。
• 変数 maxD を -1 で初期化しておきます（重複が見つからなかった場合の戻り値になります）。
• 外側のforループで配列を先頭から順に走査します。
• 内側のforループでそれ以降の要素を調べ、同じ値が存在するかどうかを確認します（if (arr[i] == arr[j])）。
• 条件が成立したら、インデックス同士の差から距離 temp = j - i - 1 を計算します。
• temp がこれまでの最大値 maxD より大きければ、maxD を更新します。
• 配列全体の走査が完了したら、maxD を返します。

この実装は二重ループを使用しているため、時間計算量は O(n²) となります。小規模〜中規模の配列には十分な手法ですが、より大きなデータを扱う場合は、ハッシュテーブルなどを活用して O(n) へ最適化することも検討するとよいでしょう。

C言語によるサンプルコード

#include <stdio.h>
#include <math.h>

int maxDistance(int arr[], int n){
    int size = n;
    int maxD = -1;
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (arr[i] == arr[j]){
                int temp = abs(j - i - 1);
                maxD = maxD > temp ? maxD : temp;
            }
    return maxD;
}

// ドライバーコード
int main(){
    int Arr[] = {1, 2, 4, 1, 3, 4, 2, 5, 6, 5};
    printf("配列内の同じ要素の2つの出現位置間の最大距離：%d", maxDistance(Arr, 10));
    return 0;
}

実行結果

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

配列内の同じ要素の2つの出現位置間の最大距離：4

このように、配列 {1, 2, 4, 1, 3, 4, 2, 5, 6, 5} の場合、値 2 がインデックス 1 と 6 の2か所に出現しており、その間の距離 4 が最大となっています。