在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

更新於：2020年8月27日

143 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告