[LeetCode]Ar561. 数组拆分 I

🚩传送门：https://leetcode-cn.com/problems/array-partition-i/

题目

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对，返回该 最大总和 。

例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

示例 1：

输入：nums = [1,4,3,2] 输出：4 解释：所有可能的分法（忽略元素顺序）为：

1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4

所以最大总和为 4

示例 2：

输入：nums = [6,2,6,5,1,2] 输出：9 解释：最优的分法为 (1, 2), (2, 5), (6, 6) min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

解题思路：贪心

我们每次选择都想选个最大的，但是最大的会被舍弃，不能选（因为 min），所以每次选第二大的。

下面数学证明：

不失一般性，我们令每一组 满足 （若不满足，交换二者即可），这样我们需要求得的总和

就等于所有 的和

接下来，我们将所有的 按照升序排序，使得 。这样一来，对于任意的

1. 它不大于
2. 它不大于
3. 由于 对于任意的 恒成立，因此 不大于

由于 不大于 中的 个元素，也不大于 中的 个元素，而这些元素都是从 中而来的。

1. 因此 在数组 中「从大到小」至少排在第 个位置
2. 因此 在数组 中「从小到大」至多排在第 个位置
3. 这里位置的编号从 开始，即

其中数组 是将数组 升序排序得到的结果，代入 式即可得到

另一方面，令 ，此时每一组 都满足 的要求，并且有 ，此时

即 式的等号是可满足的。因此所要求得的最大总和即为

复杂度分析

时间复杂度：， 是数组的长度，即为对数组 进行排序的时间复杂度。

空间复杂度： 或者 ，由不同的排序所需要的空间决定。

官方代码

class Solution {
    public int arrayPairSum(int[] nums) {
        //1.排序
        Arrays.sort(nums);
        int ans = 0;
        //2.拿第二大
        for (int i = 0; i < nums.length; i += 2) {
            ans += nums[i];
        }
        return ans;
    }
}