Pythonでターゲット要素までの最小距離を求めるプログラムの解説

配列 nums と、2つの異なる値 target（nums 内に必ず存在する）および start が与えられたとします。このとき、nums[i] = target を満たすインデックス i の中から |i - start| が最小になるものを見つけ、その値を返すのが課題です。

例として、入力が nums = [3,4,5,6,7]、target = 7、start = 2 の場合を考えてみましょう。ターゲットに一致する値は nums[4] の1つだけなので i = 4 となり、|4 - 2| = 2 が出力されます。

解法のアプローチ

この問題は、配列を先頭から順に走査しながら、ターゲットと一致する要素のうち開始位置からの距離が最も小さいものを記録していくことで解けます。手順は以下の通りです。

• 変数 minimum を無限大（infinity）で初期化する
• i を 0 から nums のサイズ未満の範囲で繰り返す
  • nums[i] が target と一致する場合
    • |i - start| が現在の minimum より小さければ、minimum を更新する
• ループ終了後、minimum を返す

それでは、実際の実装を見て理解を深めましょう。

実装例

from math import inf
def solve(nums, target, start):
   minimum = inf
   for i in range(len(nums)):
      if nums[i] == target:
         if abs(i - start) < minimum:
            minimum = abs(i - start)
   return minimum
nums = [3,4,5,6,7]
target = 7
start = 2
print(solve(nums, target, start))

入力

[3,4,5,6,7], 7, 2

出力

2

計算量について

このアルゴリズムは配列を1回だけ走査するため、時間計算量は O(n)、追加で必要なメモリは定数のみなので空間計算量は O(1) となります。線形探索によるシンプルな方法ですが、配列がソートされていない場合にも確実に動作する点が利点です。