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

สมมติว่าเรามีอาร์เรย์ที่มีค่าบวกสองตัวคือ nums1 และ nums2 ที่มีขนาดเท่ากัน ผลรวมสัมบูรณ์ของสองอาร์เรย์นี้คือผลรวมของ |nums1[i] - nums2[i]| สำหรับแต่ละ 0 <=i

ดังนั้น หากอินพุตเป็น nums1 =[2,8,6], nums2 =[3,4,6] ผลลัพธ์จะเป็น 3 เพราะเราสามารถหาวิธีแก้ปัญหาที่เหมาะสมที่สุดได้สองวิธี

• แทนที่องค์ประกอบที่ดัชนี 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.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้า nums1 เหมือนกับ nums2 แล้ว

  • กลับ(0)

• minn_diff :=-อินฟินิตี้

• ind :=-1

• สำหรับฉันในช่วง 0 ถึงขนาด nums1 - 1 ทำ

  • ถ้า |nums1[i]-nums2[i]|> minn_diff แล้ว

    • ind :=ฉัน

    • minn_diff :=|nums1[i] - nums2[i]|

• diff :=|nums1[ind] - nums2[ind]|

• ดัชนี :=ind

• สำหรับฉันในช่วง 0 ถึงขนาด nums1 - 1 ทำ

  • ถ้าฉันไม่เหมือน ind แล้ว

    • ถ้า |nums1[i] - nums2[ind]| <แตกต่าง แล้วก็

      • ดัชนี :=ผม

      • diff :=|nums1[i]-nums2[ind]|

• ผลรวม :=0

• สำหรับฉันในช่วง 0 ถึงขนาด nums1 - 1 ทำ

  • ถ้าฉันเหมือนกับ ind แล้ว

    • summ :=summ + |nums1[index] - nums2[i]|

  • มิฉะนั้น

    • summ :=summ + |nums1[i] - nums2[i]|

• คืนค่า summ mod (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