Chương trình tìm K cặp tổng lớn nhất từ 2 mảng trong Python

Cho 2 mảng nums0, nums1 và k. Tìm tổng của k cặp lớn nhất (mỗi cặp lấy 1 phần tử từ mỗi mảng).

Ví dụ: nums0=[8,6,12], nums1=[4,6,8], k=2 → 38 (cặp [12,8] và [12,6]).

Giải thuật (Max Heap + Tập visited tránh trùng)

1. Sắp xếp cả 2 mảng tăng dần.
2. Khởi tạo max-heap (dùng min-heap với giá trị âm) với cặp lớn nhất: (-(nums0[-1]+nums1[-1]), i, j).
3. Lặp k lần: pop cặp lớn nhất, cộng vào kết quả. Push 2 cặp láng giềng (i-1,j) và (i,j-1) nếu chưa visited.

Ví dụ minh họa

from heapq import heappush, heappop

class Solution:
    def solve(self, nums0, nums1, k):
        if k > len(nums0) * len(nums1):
            return 0
        nums0.sort()
        nums1.sort()
        i, j = len(nums0) - 1, len(nums1) - 1
        pq = [(-(nums0[i] + nums1[j]), i, j)]
        visited = {(i, j)}
        ans = 0
        for _ in range(k):
            s, i, j = heappop(pq)
            ans += -s
            if i > 0 and (i - 1, j) not in visited:
                visited.add((i - 1, j))
                heappush(pq, (-(nums0[i - 1] + nums1[j]), i - 1, j))
            if j > 0 and (i, j - 1) not in visited:
                visited.add((i, j - 1))
                heappush(pq, (-(nums0[i] + nums1[j - 1]), i, j - 1))
        return ans

ob = Solution()
print(ob.solve([8, 6, 12], [4, 6, 8], 2))  # Output: 38

Đầu vào / Đầu ra

Input: [8, 6, 12], [4, 6, 8], 2

Output: 38