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 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告