LeetCode #561 是一道贪心算法的 easy 题，记录这道题主要是想梳理一下数学证明的过程。贪心算法比较有趣的是，代码一般写起来都不复杂，但是证明本身才是个比较难的事情。比如在面试过程中，你可能意识到了一个题目需要用贪心算法，或者是你不好判断是否可以使用贪心算法，但是就是无法向面试官证明自己的分析。
先看题目吧：
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，
使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该最大总和
直觉是使用贪心算法，策略是：
对数组 nums 进行升序排序，依次两两分组，取各组中第一个数的和
证明过程
一般而言，可以使用反证法来验证贪心策略的正确性。
假设： 有升序排序好的数组 a，按照上面所说的策略，我们得到分组：
(a[0], a[1]), (a[2], a[3]), (a[i-1], a[i]), (a[i+1], a[i+2]), ..., (a[2n-2], a[2n-1])
由于数组是升序，故有 a[i-1] ≤ a[i] ≤ a[i+1] ≤ a[i+2]，这四个元素对应的分组中较小数求和结果为 a[i-1] + a[i+1]
重新排列从a[i-1]到a[i+2]的两个分组，共有4种可能的组合：
(a[i-1], a[i+1]), (a[i], a[i+2])，其对应各组较小数总和为a[i-1] + a[i] ≤ a[i-1] + a[i+1]；(a[i-1], a[i+2]), (a[i], a[i+1])，其对应各组较小数总和为a[i-1] + a[i] ≤ a[i-1] + a[i+1]；(a[i], a[i+1]), (a[i-1], a[i+2])，其对应各组较小数总和为a[i] + a[i-1] ≤ a[i-1] + a[i+1]；(a[i], a[i+2]), (a[i-1], a[i+1])，其对应各组较小数总和为a[i] + a[i-1] ≤ a[i-1] + a[i+1]。
即，如果不按照升序结果进行两两分组，则各组较小数的总和小于或等于按照升序结果进行两两分组的各组较小数的总和。
题解
func arrayPairSum(nums []int) int {
sort.Slice(nums, func(i, j int) bool { return nums[i] <= nums[j] })
sum := 0
for i := 0; i < len(nums); i += 2 {
sum += nums[i]
}
return sum
}
复杂度分析
- 时间复杂度：
O(nlogn+n)，nlogn是快排的时间复杂度，n是数组遍历的时间复杂度。 - 空间复杂度：
O(logn)，递归调用的内存开销。
版权声明：本文为原创文章，转载请注明来源：《贪心算法：数组拆分 LeetCode 561 - Hackerpie》，谢绝未经允许的转载。