Python程式：計算差異大於目標值的互異對數的最大值

假設我們有一個名為nums的數字列表和另一個值target。我們需要找到對數的最大值，其中對於每一對i < j，i和j都不在任何其他對中，並且|nums[i] - nums[j]| >= target。

因此，如果輸入類似於nums = [2, 4, 6, 10, 11]，target = 5，則輸出將為2，因為我們可以得到以下對：(2, 6)，(5, 10)

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

  • N := A的大小
  • 對列表A進行排序
  • ans := 0
  • j := N / 2
  • 對於i從0到N / 2，執行以下操作：
    • 當j < N且A[j] - A[i] < target時，執行以下操作：
      • j := j + 1
    • 如果j < N，則
      • ans := ans + 1
      • j := j + 1
  • 返回ans

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

示例

 線上演示

class Solution:
   def solve(self, A, target):
      N = len(A)
      A.sort()
      ans = 0
      j = N >> 1
      for i in range(N >> 1):
         while j < N and A[j] - A[i] < target:
            j += 1
         if j < N:
            ans += 1
            j += 1
      return ans
ob = Solution()
nums = [2, 4, 6, 10, 11]
target = 5
print(ob.solve(nums, target))

輸入

[2, 4, 6, 10, 11], 5

輸出

2

更新於: 2020年10月20日

212 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告