Python程式：查詢兩對數字，使其和的差最小

假設我們有一個名為 nums 的數字列表，我們希望從中選擇兩對數字，使得這兩對數字的和的絕對差最小。

因此，如果輸入類似於 nums = [3, 4, 5, 10, 7]，則輸出將為 1，因為我們可以選擇這些對 (3 + 7) - (4 + 5) = 1。

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

• distances := 新列表
• 對於 i 從 0 到 nums 大小 - 2，執行
  • 對於 j 從 i + 1 到 nums 大小 - 1，執行
    • 在 distances 的末尾插入列表 [|nums[i] - nums[j]| , i, j]
  • 對列表 distances 進行排序
  • ans := 1^9
  • 對於 i 從 0 到 distances 大小 - 2，執行
    • [dist, i1, i2] := distances[i]
    • j := i + 1
    • [dist2, i3, i4] := distances[j]
    • 當 j < distances 大小 且 (i1, i2, i3, i4) 中的元素不唯一時，執行
      • [dist2, i3, i4] := distances[j]
      • j := j + 1
    • 如果 (i1, i2, i3, i4) 中的元素唯一，則
      • ans := ans 和 (dist2 - dist) 的最小值
    • 返回 ans

讓我們看看以下實現，以便更好地理解

示例程式碼

線上演示

class Solution:
   def solve(self, nums):
      distances = []
      for i in range(len(nums) - 1):
         for j in range(i + 1, len(nums)):
            distances.append((abs(nums[i] - nums[j]), i, j))
      distances.sort()
      ans = 1e9
      for i in range(len(distances) - 1):
         dist, i1, i2 = distances[i]
         j = i + 1
         dist2, i3, i4 = distances[j]
         while j < len(distances) and len({i1, i2, i3, i4}) != 4:
            dist2, i3, i4 = distances[j]
            j += 1
         if len({i1, i2, i3, i4}) == 4:
            ans = min(ans, dist2 - dist)
      return ans

ob = Solution()
nums = [3, 4, 5, 10, 7]
print(ob.solve(nums))

輸入

[3, 4, 5, 10, 7]

輸出

1

Arnab Chakraborty

更新於: 2020年11月25日

209 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習