Tối thiểu hóa hiệu max-min của ba mảng đã sắp xếp trong Python

Cho ba mảng đã sắp xếp A, B, C (có thể kích thước khác nhau). Ta cần tìm giá trị nhỏ nhất của max(A[i], B[j], C[k]) - min(A[i], B[j], C[k]) cho mọi triplet (A[i], B[j], C[k]).

Ví dụ, với A = [2, 5, 6, 9, 11], B = [7, 10, 16], C = [3, 4, 7, 7], kết quả là 1 (chọn 6, 7, 7).

Thuật toán giải quyết

• Khởi tạo con trỏ i, j, k tại cuối các mảng.
• minimum_difference := |max(A[i], B[j], C[k]) - min(A[i], B[j], C[k])|.
• Trong khi i, j, k >= 0:
  • Tính current_diff tương tự.
  • Cập nhật minimum_difference nếu nhỏ hơn.
  • Tìm maximum_term trong ba giá trị hiện tại.
  • Giảm con trỏ của mảng chứa maximum_term.
• Trả về minimum_difference.

Ví dụ minh họa

def solve(A, B, C):
    i = len(A) - 1
    j = len(B) - 1
    k = len(C) - 1
    minimum_difference = 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_difference:
            minimum_difference = 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_difference

A = [2, 5, 6, 9, 11]
B = [7, 10, 16]
C = [3, 4, 7, 7]
print(solve(A, B, C))  # 1

Đầu vào

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

Đầu ra

1