โปรแกรมหาความต่างสัมบูรณ์รวมขั้นต่ำใน Python

สมมติว่ามีอาร์เรย์ nums1 และ nums2 ขนาดเท่ากัน และมีค่าบวก ความต่างสัมบูรณ์รวมคือผลรวมของ |nums1[i] - nums2[i]| สำหรับทุก i ตอนนี้เราสามารถแทนที่องค์ประกอบใน nums1 ได้มากสุด 1 ตัวด้วยองค์ประกอบอื่นใน nums1 เพื่อลดความต่างสัมบูรณ์รวมให้น้อยที่สุด ต้องคืนค่าความต่างสัมบูรณ์รวมขั้นต่ำหลังแทนที่ (มอดุลลอ 10^9 + 7)

ตัวอย่าง: nums1 = [2,8,6], nums2 = [3,4,6] ผลลัพธ์คือ 3 เพราะสามารถทำได้ 2 วิธี:

• แทนที่ดัชนี 1 ด้วยดัชนี 0: [2,8,6] → [2,2,6]
• แทนที่ดัชนี 1 ด้วยดัชนี 2: [2,8,6] → [2,6,6]

ทั้งคู่ให้ผลรวม |2-3| + (|2-4| หรือ |6-4|) + |6-6| = 3

วิธีแก้ปัญหา

1. ถ้า nums1 == nums2 ให้คืน 0
2. minn_diff := -infinity
3. ind := -1
4. หาดัชนี ind ที่มี |nums1[i] - nums2[i]| สูงสุด
5. diff := |nums1[ind] - nums2[ind]|, index := ind
6. หา index ที่ทำให้ |nums1[i] - nums2[ind]| น้อยที่สุด (i != ind)
7. คำนวณ summ โดยใช้ nums1[index] แทนที่ตำแหน่ง ind
8. คืนค่า summ % (10^9 + 7)

ตัวอย่างโค้ด

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))

อินพุต

[2,8,6], [3,4,6]

เอาต์พุต

3