โปรแกรมค้นหาตัวเลขสองคู่ที่ผลต่างระหว่างผลรวมของคู่เหล่านี้ถูกย่อให้เล็กสุดใน python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และเราต้องการเลือกตัวเลขสองคู่จากนั้นจึงลดความแตกต่างที่แน่นอนระหว่างผลรวมของทั้งสองคู่นี้

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[3, 4, 5, 10, 7] ผลลัพธ์จะเป็น 1 เพราะเราสามารถเลือกคู่เหล่านี้ได้ (3 + 7) - (4 + 5) =1

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

• ระยะทาง :=รายการใหม่
• สำหรับฉันในช่วง 0 ถึงขนาดของ nums - 2 ทำ
  • สำหรับ j ในช่วง i + 1 ถึงขนาดของ nums - 1 ทำ
    • แทรกรายการ [|nums[i] - nums[j]| , i, j] เมื่อสิ้นสุดระยะทาง
  • จัดเรียงรายการระยะทาง
  • ตอบ :=1^9
  • สำหรับฉันในช่วง 0 ถึงขนาดของระยะทาง - 2 ทำ
    • [dist, i1, i2] :=ระยะทาง[i]
    • j :=i + 1
    • [dist2, i3, i4] :=ระยะทาง[j]
    • ในขณะที่ j <ขนาดของระยะทางและองค์ประกอบใน (i1, i2, i3, i4) ไม่ซ้ำกัน ทำ
      • [dist2, i3, i4] :=ระยะทาง[j]
      • j :=j + 1
    • หากองค์ประกอบใน (i1, i2, i3, i4) ไม่ซ้ำกัน ดังนั้น
      • ans :=ขั้นต่ำของ ans และ (dist2 - dist)
    • คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

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

class Solution:
   def solve(self, nums):
      distances = []
      for i in range(len(nums) - 1):
         for j in range(i + 1, len(nums)):
            distances.append((abs(nums[i] - nums[j]), i, j))
      distances.sort()
      ans = 1e9
      for i in range(len(distances) - 1):
         dist, i1, i2 = distances[i]
         j = i + 1
         dist2, i3, i4 = distances[j]
         while j < len(distances) and len({i1, i2, i3, i4}) != 4:
            dist2, i3, i4 = distances[j]
            j += 1
         if len({i1, i2, i3, i4}) == 4:
            ans = min(ans, dist2 - dist)
      return ans

ob = Solution()
nums = [3, 4, 5, 10, 7]
print(ob.solve(nums))

อินพุต

[3, 4, 5, 10, 7]

ผลลัพธ์

1