C++で配列内の2つの数値間の最小距離を求める方法

はじめに

ソートされていない配列Aと、2つの数値x・yが与えられたとき、配列内におけるxとyの最小距離（インデックスの差）を求める問題を考えてみましょう。なお、配列には重複した要素が含まれている場合もあります。

例えば、配列が A = [2, 5, 3, 5, 4, 4, 2, 3]、x = 3、y = 2 である場合、3と2の間の最小距離は 1 となります。

解法のアプローチ

この問題は、配列を一度だけ走査することでO(n)の計算量で解くことができます。手順は以下の通りです。

• 配列を左から右へ走査し、xまたはyのいずれかが見つかった時点で停止します。その位置のインデックスを prev として保存します。
• 続いて、インデックス prev 以降の要素を引き続き走査します。現在のインデックス i の要素がxまたはyのいずれかに一致した場合、それが A[prev] と異なる値かどうかを確認します。異なる値であれば、必要に応じて最小距離を更新し、prev を i に更新します。同じ値であった場合も、prev を i に更新して次へ進みます。

この方法により、各要素を一度ずつ確認するだけで最小距離を求められるため、時間計算量はO(n)、追加のメモリ使用量はO(1)と非常に効率的です。

C++での実装例

#include<iostream>
using namespace std;
int findMinDistance(int A[], int n, int x, int y) {
    int i = 0;
    int distance = INT_MAX;
    int prev_index;
    for (i = 0; i < n; i++) {
        if (A[i] == x || A[i] == y) {
            prev_index = i;
            break;
        }
    }
    while (i < n) {
        if (A[i] == x || A[i] == y) {
            if ( A[prev_index] != A[i] && (i - prev_index) < distance ){
                distance = i - prev_index;
                prev_index = i;
            } else
                prev_index = i;
        }
        i++;
    }
    return distance;
}
int main() {
    int arr[] = {2, 5, 3, 5, 4, 4, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    int y = 2;
    cout << "Minimum distance between " << x << " and " << y << " is: "<< findMinDistance(arr, n, x, y);
}

出力結果

Minimum distance between 3 and 2 is: 1

まとめ

このアルゴリズムでは、最初にxまたはyのいずれかが出現する位置を記録し、その後に出現するもう一方の値との距離を順次比較することで最小距離を求めています。重複要素が含まれる配列でも正しく動作し、線形時間で処理が完了するため、大規模なデータに対しても実用的な手法です。