https://leetcode.com/problems/array-partition-i/#/description
image.png
image.png
翻译
- 将长度为2n的数组分为n组,每组2个元素称为一个pair
- 将所有pair中较小的那个元素取出来,并求和
- 如何使得求和结果最大?即如何划分pair
思路
- min[列表最小元素, 任意元素] = 列表最小元素(注意不受任意元素的影响)
- 那么sum(min[ ], min[]...)与任意元素无关
- 为了使得sum最大, 每个pair中的任意元素也要小一些,这样使得较大的元素不会被"淹没掉"进而能对sum做出较大的贡献
- 对数组进行排序, min[array[i], array[i+1]] = array[i]
- 所以只要对排序后的数组每隔以为取元素求和即可
class Solution(object):
def arrayPairSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return sum(sorted(nums)[::2])
