在Python中查找给定数组中nCr值最大的配对

假设我们有一个包含n个整数的数组arr，我们必须从数组中找到arr[i]和arr[j]，使得arr[i]Carr[j]尽可能大。如果有多个配对，则返回其中任意一个。

因此，如果输入类似于[4, 1, 2]，则输出将为4 2，因为4C1 = 4，4C2 = 6，而2C1 = 2，所以(4,2)是唯一的配对。

为了解决这个问题，我们将遵循以下步骤：

• 对列表v进行排序
• N := v[n - 1]
• 如果N mod 2与1相同，则
  • first := N / 2（整数除法）
  • second := first + 1
  • left := -1, right := -1
  • temp := -1
  • 对于范围为0到n的i，执行以下操作：
    • 如果v[i] > first，则
      • temp := i
      • 中断
    • 否则，
      • difference := first - v[i]
      • 如果difference < res1，则
        • res1 := difference
        • left := v[i]
  • right := v[temp]
  • difference1 := first - left
  • difference2 := right - second
  • 如果difference1 < difference2，则
    • 打印(N, left)
  • 否则，
    • 打印(N, right)
• 否则，
  • max := N / 2（整数除法）
  • res := 3*(10^18)
  • R := -1
  • 对于范围为0到n - 1的i，执行以下操作：
    • difference := |v[i] - max|
    • 如果difference < res且不为零，则
      • res := difference
      • R := v[i]
  • 打印(N, R)

示例

让我们来看一下下面的实现，以便更好地理解：

 在线演示

def findMatrixPair(v, n):
   v.sort()
   N = v[n - 1]
   if N % 2 == 1:
      first = N // 2
      second = first + 1
      res1, res2 = 3 * (10 ** 18), 3 * (10 ** 18)
      left, right = -1, -1
      temp = -1
      for i in range(0, n):
         if v[i] > first:
            temp = i
            break
         else:
            difference = first - v[i]
            if difference < res1:
               res1 = difference
               left = v[i]
      right = v[temp]
      difference1 = first - left
      difference2 = right - second
      if difference1 < difference2:
         print(N, left)
      else:
         print(N, right)
   else:
      max = N // 2
      res = 3 * (10 ** 18)
      R = -1
      for i in range(0, n - 1):
         difference = abs(v[i] - max)
         if difference < res:
         res = difference
         R = v[i]
      print(N, R)
v = [4,1,2]
n = len(v)
findMatrixPair(v, n)

输入

[4,1,2], 3

输出

4 2

Arnab Chakraborty

更新于：2020年8月27日

143 次浏览

开启您的职业生涯

完成课程获得认证

开始学习