สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม 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 เป็นขนาดของอาร์เรย์
- เรียงลำดับอาร์เรย์
- answer := 0
- สำหรับ i ในช่วง 0 ถึง n ก้าวละ 2:
- answer := answer + array[i]
- คืนค่า answer
ตัวอย่างโค้ด
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
