0561. Array Partition
=====================
题目信息
--------
:题号: 0561
:难度: Easy
:主题: 偶数长度数组、两两分组、较小值之和、最大化
:原题: `LeetCode 0561 `_
:重点: 所有元素必须恰好分入 n 个二元组、每组贡献较小值、返回最大可能总和
题目重述
--------
给定一个长度为 ``2n`` 的整数数组 ``nums``,需要把全部元素划分为 ``n`` 个二元组 ``(a_i, b_i)``。每个数组位置必须恰好属于一个二元组。
每组贡献 ``min(a_i, b_i)``,返回所有组贡献之和能够达到的最大值。相同数值位于不同下标时仍是不同元素,必须分别参与分组。
自建示例
--------
六个元素分成三组:
.. code-block:: text
输入:nums = [1,4,3,2,7,6]
输出:10
解释:可分为 (1,2)、(3,4)、(6,7),较小值之和为 1+3+6=10,并且无法取得更大总和。
包含负数:
.. code-block:: text
输入:nums = [-4,-1,2,3]
输出:-2
解释:分组 (-4,-1) 与 (2,3) 的较小值之和为 -4+2=-2,是最大结果。
排序后相邻配对保留更多较小值
----------------------------
排序数组后把相邻元素配成一对。若跨越配对让一个较大的元素成为某组最小值,就会放弃一个本可保留的较小值;交换配对可以不降低总和,反复交换后得到相邻配对。因此排序后每隔一个元素累加就是最优值。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int arrayPairSum(std::vector& nums) {
std::sort(nums.begin(), nums.end());
int answer = 0;
for (int i = 0; i < static_cast(nums.size()); i += 2) {
answer += nums[i];
}
return answer;
}
};
代码分析
--------
每一对的贡献是其较小者,排序相邻配对能让每个较小者尽量不被更大的元素替代;这是最大化保留下界的贪心结构。排序耗时 ``O(n log n)``,扫描为 ``O(n)``,额外空间为 ``O(1)``(不计排序栈)。