สมมติว่าเรามีอาร์เรย์จำนวน 2n จำนวนเต็ม เราต้องจัดกลุ่มจำนวนเต็มเหล่านี้เป็นจำนวนเต็ม n คู่ เช่น (a1, b1), (a2, b2), ..., (an, bn) ซึ่งมีผลรวมของ min (ai, bi) สำหรับ i ทั้งหมดในช่วง 1 ถึง n ให้มากที่สุด ดังนั้นหากอินพุตคือ [1, 4, 3, 2] เอาต์พุตจะเป็น 4 ดังนั้น n คือ 2 และผลรวมสูงสุดของคู่คือ 4 นี่คือ min(1, 2) + min(3, 4) =4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ให้ n คือขนาดของอาร์เรย์
- จัดเรียงอาร์เรย์
- คำตอบ :=0
- สำหรับฉันในช่วง 0 ถึง n ให้กระโดด 2
- answer :=answer + array[i]
- ส่งคืนคำตอบ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution(object): def arrayPairSum(self, a): """ :type nums: List[int] :rtype: int """ n = len(a) a.sort() ans = 0 for i in range(0,n,2): ans += a[i] return ans ob1 = Solution() print(ob1.arrayPairSum([1,4,3,2]))
อินพุต
[1,4,3,2]
ผลลัพธ์
4
