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)``(不计排序栈)。