โปรแกรมค้นหาจำนวนคู่ K-sum สูงสุดใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums และอีกค่าหนึ่งคือ k ในการดำเนินการครั้งเดียว เราสามารถเลือกสององค์ประกอบจาก num ที่ผลรวมเท่ากับ k และลบออกจากอาร์เรย์ เราต้องหาจำนวนการดำเนินการสูงสุดที่เราสามารถทำได้บนอาร์เรย์

ดังนั้น หากอินพุตเท่ากับ nums =[8,3,6,1,5] k =9 ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถลบ [3,6] ซึ่งมีผลรวมเป็น 9 แล้วจึงลบ [8,1 ] ซึ่งผลรวมเท่ากับ 9.

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

• ตัวนับ :=ความถี่ในการถือแผนที่ของแต่ละรายการเป็นตัวเลข
• res :=0
• สำหรับแต่ละ num ในเคาน์เตอร์ ทำ
  • ถ้าตัวนับ[k-num] ไม่ใช่ศูนย์ ดังนั้น
    • ถ้า num ไม่เหมือนกับ k - num แล้ว
      • res :=res + ค่าต่ำสุดของตัวนับ[num] และตัวนับ[k-num]
      • ตัวนับ[k-num] :=0
      • ตัวนับ[num] :=0
    • มิฉะนั้น
      • res :=res + ผลหารของ (ตัวนับ[num] / 2)
• ผลตอบแทน

ตัวอย่าง

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

from collections import Counter
def solve(nums, k):
   counter = Counter(nums)
   res = 0
   for num in counter:
      if counter.get(k-num, 0):
         if num != k - num:
            res += min(counter[num], counter[k-num])
            counter[k-num] = 0
            counter[num] = 0
         else:
            res += int(counter[num] / 2)

   return res

nums = [8,3,6,1,5]
k = 9
print(solve(nums, k))

อินพุต

[8,3,6,1,5], 9

ผลลัพธ์

2