在Python中查找临近元素索引最小可能的差

在Python中查找临近元素索引最小可能的差

假设我们有一个数字列表nums,我们可以说当nums[i] ≤ nums[j]时,两个数字nums[i]和nums[j]是相邻的,当nums中不存在(nums[i], nums[j])时。我们必须找到可能最小的|j – i|,使得nums[j]和nums[i]是相邻的。

因此,如果输入是nums = [1, – 9, 6, – 6, 2],那么输出将是2,因为我们可以看到2和6是相邻的,并且它们相隔2个索引。

要解决此问题,我们将遵循以下步骤:

  • 让indexes为一个新的map。

  • 对于A中的每个索引i和值x,执行以下操作:

    • 在indexes[x]的末尾插入i。
  • 让ans为A的大小。

  • 对于indexes中所有值的列表中的每一行,执行以下操作:

    • 对于所有范围从0到行大小-2的i,执行以下操作:
      • ans := ans和(row[i + 1] – row[i])的最小值。
  • 令vals为排序后的索引列表。

  • 对于k从0到vals大小-2,执行以下操作:

    • 让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相关文章,请阅读:Python 教程

示例(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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程