清丰网站建设公司,如何选择最好的域名,专业SEO教程网站,google关键词搜索工具题目描述解题思路执行结果 leetcode 561. 数组拆分 题目描述 数组拆分 给定长度为 2n 的整数数组 nums #xff0c;你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) #xff0c;使得从 1 到 n 的 min(ai, bi) 总和最大。 返回该 最大总和 。 示例 1你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) 使得从 1 到 n 的 min(ai, bi) 总和最大。 返回该 最大总和 。 示例 1 输入nums [1,4,3,2] 输出4 解释所有可能的分法忽略元素顺序为 (1, 4), (2, 3) - min(1, 4) min(2, 3) 1 2 3 (1, 3), (2, 4) - min(1, 3) min(2, 4) 1 2 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 解题思路 法1 方法1 排序\ 将数字分成n组,计算每组最小的值的和,和最大时既是我们最终的返回值, 所以我们要得到最大的和值,就可以先排序 然后依次加0,2,4...2n-2位置的数就是最大的和值 时间复杂度(O(nlogn)) 空间复杂度(O(1)) 执行结果 法1 // 最大分组func arrayPairSum(nums []int) (r int) { sort.Ints(nums) for i : 0; i len(nums); i 2 { r nums[i] } return} 执行结果 通过 显示详情 查看示例代码 添加备注 执行用时 52 ms , 在所有 Go 提交中击败了 75.95% 的用户 内存消耗 6.4 MB , 在所有 Go 提交中击败了 67.09% 的用户 通过测试用例 83 / 83 炫耀一下: 本文由 mdnice 多平台发布
