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

Arnab Chakraborty

更新于: 2020年10月20日

212 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习