0561. 数组拆分 #
- 标签:数组
- 难度:简单
题目大意 #
描述:给定一个长度为 2 * n
的整数数组 nums
。
要求:将数组中的数拆分成 n
对,每对数求最小值,求 n
对数最小值的最大总和是多少。
说明:
- $1 \le n \le 10^4$。
- $nums.length == 2 * n$。
- $-10^4 \le nums[i] \le 10^4$。
示例:
|
|
解题思路 #
思路 1:排序 #
要想每对数最小值的总和最大,就得使每对数的最小值尽可能大。只有让较大的数与较大的数一起组合,较小的数与较小的数一起结合,才能才能使总和最大。
- 对
nums
进行排序。 - 将相邻两个元素的最小值进行相加,即得到结果。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n \times \log_2n)$。
- 空间复杂度:$O(1)$。