Chương trình Python tìm cặp gần nhất từ 2 mảng đã sắp xếp

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho hai mảng, cần tìm cặp gần nhất (closest pair) từ 2 mảng đã sắp xếp.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

# sys module
import sys

# tìm cặp
def print_(ar1, ar2, m, n, x):
    # độ chênh lệch
    diff = sys.maxsize
    # chỉ số
    l = 0
    r = n - 1
    while (l < m and r >= 0):
        # cặp gần nhất
        if abs(ar1[l] + ar2[r] - x) < diff:
            res_l = l
            res_r = r
            diff = abs(ar1[l] + ar2[r] - x)
        # tổng cặp
        if ar1[l] + ar2[r] > x:
            r = r - 1
        else:
            l = l + 1
    # In kết quả
    print("Cặp gần nhất là [", ar1[res_l], ",", ar2[res_r], "]")

# main
ar1 = [1, 3, 6, 9]
ar2 = [11, 23, 35, 50]
m = len(ar1)
n = len(ar2)
x = 20
print_(ar1, ar2, m, n, x)

Kết quả

Cặp gần nhất là [ 9 , 11 ]

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python tìm cặp gần nhất từ 2 mảng đã sắp xếp.