561 数组拆分 I（贪心）

我不是女神ヾ 2022-08-31 07:21 170阅读 0赞

**1. 问题描述：**

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该最大总和 。

**示例 1：**

输入：nums = \[1,4,3,2\]  
输出：4  
解释：所有可能的分法（忽略元素顺序）为：  
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3  
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3  
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4  
所以最大总和为 4

**示例 2：**

输入：nums = \[6,2,6,5,1,2\]  
输出：9  
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

**提示：**  
1 <= n <= 10 ^ 4  
nums.length == 2 \* n  
\-10 ^ 4 <= nums\[i\] <= 10 ^ 4  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/array-partition-i

**2. 思路分析：**

因为数组中的元素在配对的时候与在数组中的顺序是没有关系的，所以我们可以先对数组排个序这样可以找一下规律，排序之后依次考虑配对的顺序，我们可以先考虑前面两个较小的数字看一下他们的配对顺序，可以发现较小的两个数字配对之后删除元素的总和是更小的，也即剩下来的元素总和是更大的，因为如果一开始a不与b配对，与其他的数字配对那么经过交换配对的顺序之后可以发现交换之后删除的元素总和是更小的，也即剩下来的结果是更大的，所以较小的两个数字配对的结果是更优的，同理我们依次可以得到剩余的数字也是相邻两个较小的数字配对能够获得更优的结果，所以我们对nums排序之后依次取较小的那个值累加起来即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def arrayPairSum(self, nums: List[int]) -> int:
            res = 0
            nums.sort()
            for i in range(0, len(nums), 2):
                res += nums[i]
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/a8a7c730185e4a87ab36736b3b5d2ebb.png