Pythonで隣接する要素のインデックスの可能な最小の違いを見つけるためのプログラム

numsの数のリストがあるとすると、numsの間に数がない場合（nums [i]、nums [j]）、2つの数nums[i]≤nums[j]が隣接していると言えます。可能な限り最小の|j--i|を見つける必要がありますnums[j]とnums[i]が隣接するようにします。

したがって、入力がnums =[1、-9、6、-6、2]の場合、出力は2になります。これは、2と6が隣接しており、互いに2つのインデックスが離れていることがわかります。

これを解決するには、次の手順に従います-

• インデックス：=新しいマップ

• Aの各インデックスiと値xについて、実行します

  • インデックスの最後にiを挿入します[x]

• ans：=Aのサイズ

• インデックスのすべての値のリストの各行について、実行します

  • 0から行のサイズまでの範囲のiの場合-2、実行

    • ans：=ansの最小値と（row [i + 1] --row [i]）

• vals：=リストインデックスを並べ替える

• 0からvals-2のサイズまでの範囲のkの場合、実行

  • r1：=インデックス[vals [k]]

  • r2：=インデックス[vals [k + 1]]

  • i：=j：=0

  • i

    • ans：=最小のansおよび| r1 [i] --r2 [j] |

    • r1 [i]

      • i：=i + 1

    • それ以外の場合

      • j：=j + 1

• ansを返す

例（Python）

理解を深めるために、次の実装を見てみましょう-

from collections import defaultdict
class Solution:
   def solve(self, A):
      indexes = defaultdict(list)
      for i, x in enumerate(A):
         indexes[x].append(i)
      ans = len(A)
      for row in indexes.values():
         for i in range(len(row) - 1):
            ans = min(ans, row[i + 1] - row[i])
      vals = sorted(indexes)
      for k in range(len(vals) - 1):
         r1 = indexes[vals[k]]
         r2 = indexes[vals[k + 1]]
         i = j = 0
         while i < len(r1) and j < len(r2):
            ans = min(ans, abs(r1[i] - r2[j]))
            if r1[i] < r2[j]:
               i += 1
            else:
               j += 1
      return ans
ob = Solution()
nums = [1, -9, 6, -6, 2]
print(ob.solve(nums))

入力

[1, -9, 6, -6, 2]

出力

2