โปรแกรมหาอาร์เรย์ผลรวมเท่ากันด้วยการดำเนินการน้อยที่สุดใน Python

สมมติว่าเรามีอาร์เรย์สองอาร์เรย์ชื่อ nums1 และ nums2 ค่าในอาร์เรย์อยู่ระหว่าง 1 ถึง 6 (รวม) ในหนึ่งการดำเนินการ เราสามารถอัปเดตค่าใดก็ตามในอาร์เรย์ใดก็ตามเป็นค่าใดก็ตามระหว่าง 1 ถึง 6 เราต้องหาจำนวนการดำเนินการน้อยที่สุดที่จำเป็นเพื่อให้ผลรวมค่าใน nums1 เท่ากับผลรวมค่าใน nums2 ต้อง return -1 ถ้าไม่เป็นไปได้

เช่น ถ้าอินพุตคือ nums1 = [1,5,6], nums2 = [4,1,1] ผลลัพธ์จะเป็น 2 เพราะเราสามารถเปลี่ยน nums2 จาก [4,1,1] เป็น [4,1,6] ในครั้งแรก และ [4,2,6] ในครั้งที่สอง เพื่อให้ผลรวมเท่ากับ nums1

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

• s1 := ผลรวมทุกองค์ประกอบใน nums1
• s2 := ผลรวมทุกองค์ประกอบใน nums2
• เรียง nums1 และ nums2
• ถ้า s1 > s2: สลับ nums1 กับ nums2 และ s1 กับ s2
• ans := 0
• left := 0, right := ขนาดของ nums2 - 1
• while left < ความยาวของ nums1 หรือ right >= 0:
  • ถ้า s1 เท่ากับ s2: return ans
  • curr_left := nums1[left] ถ้า left < ความยาว nums1 มิฉะนั้น 7
  • curr_right := nums2[right] ถ้า right >= 0 มิฉะนั้น 0
  • ถ้า 6-curr_left >= curr_right-1:
    • s1 := s1 + min(6-curr_left, s2-s1)
    • left := left + 1
  • มิฉะนั้น:
    • s2 := s2 - min(curr_right-1, s2-s1)
    • right := right - 1
  • ans := ans + 1
• return -1 ถ้า s1 ไม่เท่ากับ s2 มิฉะนั้น ans

ตัวอย่าง

def solve(nums1, nums2):
    s1 = sum(nums1)
    s2 = sum(nums2)
    nums1.sort()
    nums2.sort()
    if s1 > s2:
        nums1, nums2 = nums2, nums1
        s1, s2 = s2, s1
    ans = 0
    left, right = 0, len(nums2)-1
    while left < len(nums1) or right >= 0:
        if s1 == s2:
            return ans
        curr_left = nums1[left] if left < len(nums1) else 7
        curr_right = nums2[right] if right >= 0 else 0
        if 6 - curr_left >= curr_right - 1:
            s1 += min(6 - curr_left, s2 - s1)
            left += 1
        else:
            s2 -= min(curr_right - 1, s2 - s1)
            right -= 1
        ans += 1
    return -1 if s1 != s2 else ans

nums1 = [1,5,6]
nums2 = [4,1,1]
print(solve(nums1, nums2))

อินพุต

[1,5,6], [4,1,1]

เอาต์พุต

2