Chương trình tìm tổng chênh lệch tuyệt đối tối thiểu trong Python

Mô tả bài toán

Cho hai mảng nums1 và nums2 cùng kích thước, chỉ chứa giá trị dương. Tổng chênh lệch tuyệt đối là tổng của |nums1[i] - nums2[i]| cho mọi 0 <= i < n. Chúng ta có thể thay thế tối đa một phần tử của nums1 bằng bất kỳ phần tử nào khác trong nums1 để tối thiểu hóa tổng chênh lệch tuyệt đối. Hãy tìm giá trị tối thiểu này modulo 10^9 + 7.

Ví dụ

Nếu đầu vào là nums1 = [2,8,6], nums2 = [3,4,6], thì đầu ra sẽ là 3 vì:

Thay phần tử tại chỉ số 1 bằng phần tử tại chỉ số 0: [2,8,6] => [2,2,6].
Hoặc thay phần tử tại chỉ số 1 bằng phần tử tại chỉ số 2: [2,8,6] => [2,6,6].

Cả hai đều cho tổng chênh lệch: |2-3| + (|2-4| hoặc |6-4|) + |6-6| = 3.

Giải thuật

Nếu nums1 == nums2, trả về 0.
Tìm chỉ số ind nơi chênh lệch |nums1[i] - nums2[i]| lớn nhất.
Tìm chỉ số index (khác ind) sao cho |nums1[index] - nums2[ind]| nhỏ nhất.
Tính tổng chênh lệch mới với thay thế tại ind bằng nums1[index].
Trả về kết quả modulo 10^9 + 7.

Triển khai Python

def solve(nums1, nums2):
    if nums1 == nums2:
        return 0
    minn_diff = float('-inf')
    ind = -1
    for i in range(len(nums1)):
        if abs(nums1[i] - nums2[i]) > minn_diff:
            ind = i
            minn_diff = abs(nums1[i] - nums2[i])
    diff = abs(nums1[ind] - nums2[ind])
    index = ind
    for i in range(len(nums1)):
        if i != ind:
            if abs(nums1[i] - nums2[ind]) < diff:
                index = i
                diff = abs(nums1[i] - nums2[ind])
    summ = 0
    for i in range(len(nums1)):
        if i == ind:
            summ += abs(nums1[index] - nums2[i])
        else:
            summ += abs(nums1[i] - nums2[i])
    return summ % (10**9 + 7)

nums1 = [2, 8, 6]
nums2 = [3, 4, 6]
print(solve(nums1, nums2))

Đầu vào