0561-数组拆分

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

给定长度为 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 <= n <= 104
  • nums.length == 2 * n
  • -104 <= nums[i] <= 104

方法一：排序

思路与算法

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

\sum_{i=1}^n \min(a_i, b_i)

就等于所有 a_i 的和

\sum_{i=1}^n a_i \tag{1}

接下来，我们将所有的 (a_i, b_i) 按照升序排序，使得 a_1 \leq a_2 \leq \cdots \leq a_n。这样一来，对于任意的 a_j

  • 它不大于 a_{j+1}, a_{j+2}, \cdots, a_n；

  • 它不大于 b_j；

  • 由于 a_i \leq b_i 对于任意的 i 恒成立，因此它不大于 b_{j+1}, b_{j+2}, \cdots, b_n。

由于 a_j 不大于 {a\ 中的 n-j 个元素，也不大于 {b\ 中的 n-j+1 个元素，而这些元素都是从 nums 中而来的，因此 a_j 在数组 nums 中「从大到小」至少排在第 (n-j) + (n-j+1) + 1 = 2(n-j+1) 个位置，也就是「从小到大」至多排在第 2n - 2(n-j+1) + 1 = 2(j-1) + 1 个位置，这里位置的编号从 1 开始，即

a_j \leq c_{2(j-1)+1}

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

\sum_{i=1}^n a_i \leq \sum_{i=1}^n c_{2(i-1)+1} \tag{2}

另一方面，令 (a_1, b_1) = (c_1, c_2), (a_2, b_2) = (c_3, c_4), \cdots, (a_n, b_n) = (c_{2n-1}, c_{2n})，此时每一组 (a_i, b_i) 都满足 a_i \leq b_i 的要求，并且有 a_1 \leq a_2 \leq \cdots \leq a_n，此时

\sum_{i=1}^n a_i = \sum_{i=1}^n c_{2(i-1)+1}

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

\sum_{i=1}^n c_{2(i-1)+1}

代码

需要注意大部分语言的数组编号是从 0（而不是上文中的 1）开始的。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            ans += nums[i];
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < nums.length; i += 2) {
            ans += nums[i];
        }
        return ans;
    }
}
[sol1-Python3]
1
2
3
4
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])
[sol1-JavaScript]
1
2
3
4
5
6
7
8
var arrayPairSum = function(nums) {
    nums.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0; i < nums.length; i += 2) {
        ans += nums[i];
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
func arrayPairSum(nums []int) (ans int) {
    sort.Ints(nums)
    for i := 0; i < len(nums); i += 2 {
        ans += nums[i]
    }
    return
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
int cmp(int *a, int *b) {
    return *a - *b;
}

int arrayPairSum(int *nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int ans = 0;
    for (int i = 0; i < numsSize; i += 2) {
        ans += nums[i];
    }
    return ans;
}

复杂度分析

  • 时间复杂度：O(n\log n)，即为对数组 nums 进行排序的时间复杂度。

  • 空间复杂度：O(\log n)，即为排序需要使用的栈空间。

 Comments
On this page
0561-数组拆分