#561. Array Partition I

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])
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容