LeetCode题解之数组拆分 I

数组拆分 I

题目描述

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。

示例 1：

输入: [1,4,3,2]

输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).

提示：

1. n 是正整数,范围在 [1, 10000].
2. 数组中的元素范围在 [-10000, 10000].

解题思路

要想获取最大总和，只需要将数组按从小到大的顺序进行拆分即可，因此我们可以对给定数组的元素进行排序，并直接按排序顺序形成元素的配对，选取每个配对的第一个元素即可。

复杂度分析

• 时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(1)。

代码实现

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < nums.length; i += 2) {
            res += nums[i];
        }
        return res;
    }
}