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