leetcode561

绝地灬酷狼 2022-05-26 12:41 132阅读 0赞

# leetcode 561 习题解答 #

原题网址见

[https://leetcode.com/problems/array-partition-i/description/][https_leetcode.com_problems_array-partition-i_description]

## 题目描述 ##

Given an array of 2n  2 n  integers, your task is to group these integers into n pairs of integer, say (a1  a 1 , b1  b 1 ), (a2  a 2 , b2  b 2 ), …, (an  a n , bn  b n ) which makes sum of min(ai  a i , bi  b i ) for all i from 1 to n as large as possible.

## 题目分析 ##

这里要求对2n  2 n 个数字进行配对，并且对每一对数字，取出他们中的最小者，并且对这些最小者进行求和得出最大的和。

求最大的和，这是这道题最关键的突破点。如何在两两取最小值的情况下得出尽可能大的和呢？

注意到样例，1，3，4，2这四个数字中，我们来探究(1,2)(3,4)与(1,3)(2,4)这两种不同的组合的差别。

(1,3)之所以是比(1,2)这个组合要差，一个很重要的原因是在(1,3)中取最小值的时候，从3到1，损失了2，而相比起这个，(1,2)只损失了1。这里损失的减少，带来的直接好处就是最后和能尽可能大。

因此，为了和尽可能大，我们要做的是，每一对数中的两个数之间的差要尽可能小，这样子求和加起来的时候损失就能够达到最小，从而求和最大，而能够让两个数之间的差尽可能小的排列很明显，一定是按序排好的情况。

## 代码展示 ##

class Solution:
        def arrayPairSum(self, nums):
            """ :type nums: List[int] :rtype: int """
            sort_nums = sorted(nums)
            ss = 0
            for i in sort_nums[::2]:
                ss += i
            return ss

这里用到了一个切片的技巧，减少了很多代码量。  
`sort_nums[::2]`能够做到从原有的列表中隔一个取一个，这样子就必然能够取到每对数中最小的那一个数。

[https_leetcode.com_problems_array-partition-i_description]: https://leetcode.com/problems/array-partition-i/description/