Python中三個不同已排序陣列的最小化 (max(A[i], B[j], C[k]) – min(A[i], B[j], C[k]))

假設我們有三個已排序的陣列 A、B 和 C（這些陣列的大小可能不同），我們需要找到計算任何三元組 (A[i], B[j], C[k]) 的最大值和最小值之間的最小絕對差，其中它們分別屬於陣列 A、B 和 C。

因此，如果輸入類似於 A：[2, 5, 6, 9, 11]，B：[7, 10, 16]，C：[3, 4, 7, 7]，則輸出將為 1，因為透過選擇 A[i] = 6，B[j] = 7 和 C[k] = 7，我們將得到最小差值為 max(A[i], B[j], C[k]) - min(A[i], B[j], C[k])) = |7-6| = 1

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

  • i := A 的大小 - 1
  • j := B 的大小 - 1
  • k := C 的大小 - 1
  • minimum_difference := |A[i]、B[j]、C[k] 的最大值 - A[i]、B[j]、C[k] 的最小值|
  • 當 i 不等於 -1 且 j 不等於 -1 且 k 不等於 -1 時，執行以下操作：
    • current_diff := |A[i]、B[j]、C[k] 的最大值 - A[i]、B[j]、C[k] 的最小值|
    • 如果 current_diff < minimum_difference 且 minimum_difference 非零，則：
      • minimum_difference := current_diff
    • maximum_term := A[i]、B[j]、C[k] 的最大值
    • 如果 A[i] 等於 maximum_term，則：
      • i := i - 1
    • 否則，如果 B[j] 等於 maximum_term，則：
      • j := j - 1
    • 否則：
      • k := k - 1
  • 返回 minimum_difference

示例

讓我們來看下面的實現，以便更好地理解：

線上演示

def solve(A, B, C):
   i = len(A) - 1
   j = len(B) - 1
   k = len(C) - 1
   minimum_dfference = abs(max(A[i], B[j], C[k]) - min(A[i], B[j], C[k]))
   while i != -1 and j != -1 and k != -1:
      current_diff = abs(max(A[i], B[j], C[k]) - min(A[i], B[j], C[k]))
      if current_diff < minimum_dfference:
         minimum_dfference = current_diff
      maximum_term = max(A[i], B[j], C[k])
      if A[i] == maximum_term:
         i -= 1
      elif B[j] == maximum_term:
         j -= 1
      else:
         k -= 1
   return minimum_dfference
A = [ 2, 5, 6, 9, 11 ]
B = [ 7, 10, 16 ]
C = [ 3, 4, 7, 7 ]
print(solve(A, B, C))

輸入

A = [ 2, 5, 6, 9, 11 ] B = [ 7, 10, 16 ] C = [ 3, 4, 7, 7 ]

輸出

1

更新於：2020年8月27日

瀏覽量：175

開啟你的職業生涯

完成課程並獲得認證

開始學習
廣告