数组拆分 I

发表于 | 分类于 |
字数统计: 368 字 | 阅读时长 ≈ 1 分钟

题目描述：给定长度为 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
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

方法一：排序

  1. 先将输入数组排序
  2. 定义一个sum作为答案返回
  3. 从数组第一个元素开始，将该元素加入sum，同时i += 2以间隔取值。
  4. 最后返回sum就好啦
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int arrayPairSum(int[] nums) {
       Arrays.sort(nums);
       int sums = 0;
       for(int i = 0; i < nums.length - 1; i+=2) {
           sums += nums[i];
       }
       return sums;
    }
}

复杂度分析

  • 时间复杂度：O(nlogn)，即为对数组 nums 进行排序的时间复杂度。
  • 空间复杂度：O(logn)，即为排序需要使用的栈空间。

执行结果：通过

  • 执行用时：13 ms, 在所有 Java 提交中击败了97.93%的用户

  • 内存消耗：40.9 MB, 在所有 Java 提交中击败了12.34%的用户