Python程式：查詢相鄰元素索引的最小可能差值

假設我們有一個數字列表nums，如果列表中nums[i]和nums[j]之間沒有任何數字，則稱nums[i] ≤ nums[j]為相鄰數字。我們需要找到最小的|j - i|，使得nums[j]和nums[i]相鄰。

例如，如果輸入是nums = [1, -9, 6, -6, 2]，則輸出為2，因為我們可以看到2和6是相鄰的，它們彼此相隔2個索引。

為了解決這個問題，我們將遵循以下步驟：

  • indexes := 一個新的對映

  • 對於A中的每個索引i和值x，執行：

    • 將i插入indexes[x]的末尾

  • ans := A的大小

  • 對於indexes所有值的列表中的每一行，執行：

    • 對於範圍從0到行大小-2的i，執行：

      • ans := ans和(row[i + 1] - row[i])的最小值

  • vals := 對indexes列表進行排序

  • 對於範圍從0到vals大小-2的k，執行：

    • r1 := indexes[vals[k]]

    • r2 := indexes[vals[k + 1]]

    • i := j := 0

    • 當i < r1的大小且j < r2的大小時，執行：

      • ans := ans和|r1[i] - r2[j]|的最小值

      • 如果r1[i] < r2[j]，則

        • 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

更新於：2020-12-22

200 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告