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

开启你的职业生涯

完成课程并获得认证

开始学习
广告