LeetCode 561. 数组拆分
题目描述
题意分析
将数组中的全部元素两两配对，使每对较小值的总和最大。数组长度为偶数，每个元素必须使用一次；数值可以为负，不能为了增大结果而丢弃某些元素。
解法：排序后相邻配对
核心思路
[!blue]
每一对只有较小值计入答案，较大值相当于没有直接贡献。排序后把相邻元素配对，可以让较大的有效贡献尽量保留下来；这个结论可以通过交换两组来证明。
设剩余元素的最大值为
b、次大值为a。如果它们已经成对，无需调整；否则设它们分别与x、y配对。因为x、y都不大于a，原来两组的贡献为x + y。改成(a, b)与(x, y)后，贡献为a + min(x, y)，而a >= max(x, y)，所以新贡献不小于原贡献，其他组完全不受影响。因此总能把一个最优方案调整成“最大的两个数成对”。移除这两个数，对剩余元素重复相同论证，就得到升序排序后相邻两项成对的最优方案。每对中左侧较小，所以累加下标
0、2、4、...即可，无需实际构造各个数对。证明只用到了大小关系，不依赖数值为正，也允许重复元素。因此遇到负数仍正常相加，最终答案可以为负。
解题步骤
- 对数组进行升序排序。
- 从下标零开始，每次跨过两个元素，把当前位置的值加入总和。
- 遍历结束后返回总和，它恰好是所有相邻数对的较小值之和。
代码实现
class Solution {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length; i += 2) {
// 排序后相邻两项成组，偶数下标正是每组较小值。
sum += nums[i];
}
return sum;
}
}
import "sort"
func arrayPairSum(nums []int) int {
sort.Ints(nums)
sum := 0
for i := 0; i < len(nums); i += 2 {
// 排序后相邻两项成组，偶数下标正是每组较小值。
sum += nums[i]
}
return sum
}
复杂度分析
- 时间复杂度：$O(N\log(N+1))$，其中
N为数组长度。排序占主要成本，随后扫描为 $O(N)$。- 空间复杂度：求和部分为 $O(1)$，排序工作区依标准库实现而定；输入数组会被原地重排。
关键点总结
[!green]
- 交换论证比较的是两组总贡献，而不是单独让某一组的较小值最大。
- 最大两数可以安全成对，重复这一结论就得到相邻配对。
- 偶数下标是排序后每组的较小值，负数也参与总和。
易错点总结
[!yellow]
- 未排序就取偶数下标，没有得到最优配对的依据。
- 升序排序后累加奇数下标，取到的是各组较大值。
- 首尾配对会让较大的数与很小的数绑定，可能损失本可保留的较小值贡献。
- 把负答案截为零违反全部元素必须参与配对的要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1877. 数组中最大数对和的最小值 | 中等 | 同样把全部元素两两配对，原题最小化最大数对和而倾向首尾配，本题最大化较小值总和而配相邻项。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！