这是悦乐书的第 262 次更新, 第 275 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 129 题 (顺位题号是 561). 给定一个 2n 个整数的数组, 你的任务是将这些整数分组为 n 对整数, 比如说(a1,b1),(a2,b2),...,(an,bn), 找出每对(ai, bi) 中最小值, 然后相加, 使得其和最大. 例如:
输入:[1,4,3,2]
输出: 4
说明: n 为 2, 对的最大总和为 4 = min(1,2)+ min(3,4).
注意:
n 是正整数, 其范围为[1,10000].
数组中的所有整数都在 [-10000,10000] 的范围内.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
题目要求我们计算每两个数中最小数之和的最大值. 以题目中的数组为例,{1,4,2,3}, 四个数组成任意两对组合:
{(1,4),(2,3)}, 最小值之和为 1+2=3
{(1,2),(4,3)}, 最小值之和为 1+3=4
{(1,3),(4,2)}, 最小值之和为 1+2=3
可以发现只有 {(1,2),(4,3)} 这一对的结果是最大的, 从另外一个角度来讲, 要想最后的和最大, 那么每对数之间的差就要越小, 因为两数之间差越大, 大的数就被 pass 掉了, 无法在后面的配对中起作用. 所以, 要想每对数之间的差越小, 可以通过排序来完成, 取相邻的数作为一对, 计算最小值之和, 也就变成求奇数位元素值之和了.
此解法的时间复杂度是 O(n log(n)), 空间复杂度是 O(1).
- public int arrayPairSum(int[] nums) {
- Arrays.sort(nums);
- int sum = 0;
- for (int i=0; i<nums.length; i += 2) {
- sum += nums[i];
- }
- return sum;
- }
03 第二种解法
对于第一种解法, 我们可以使用记数排序法, 将时间复杂度降到 O(n), 但是要牺牲一定的空间.
记数排序法, 在这里大致讲下, 不展开. 对于有限个数的整数数组, 如果知道每个元素前面有多少位(排第几位), 我们可以很快速的做出排序.
比如 {1,7,5,2,8,2,7}, 使用一个长度为 9 的新数组(初始值为 0) 来记数,{0,1,2,0,0,1,0,2,1}, 其中不为 0 的数分别表示 1 个 1,2 个 2,1 个 5,2 个 7,1 个 8, 然后按照依次出现的次数打印出来 (跳过元素值为 0 的索引) 就变成{1,2,2,5,7,7,8}, 也就实现了排序.
这第二种解法就是利用记数排序来替换原来的比较排序, 此解法的时间复杂度是 O(n), 最坏的情况是 O(n+k), 其中 k 是整数的范围, 空间复杂度是 O(n).
- public int arrayPairSum2(int[] nums) {
- // 原数组大小为 20000, 我们比它多一位即可
- int[] temp = new int[20001];
- // 原数组元素的取值范围是[-10000,10000], 以旧数组的元素值作为索引, 不能存在负值, 所以加上 10000
- // 统计每个元素出现的次数
- for (int i=0; i<nums.length; i++) {
- temp[nums[i]+10000]++;
- }
- // 新建一个和原数组大小一致的数组, 来承接排序后的新元素值
- int[] temp2 = new int[nums.length];
- // 新数组 temp2 的索引值
- int index = 0;
- for (int i=0; i<temp.length; i++) {
- // 只有 temp 的元素不为 0, 说明遇到了 nums 的元素
- if (temp[i] != 0) {
- // 表明出现了 temp[i]次的 nums 中的元素(i-10000),
- for (int j=0; j<temp[i]; j++) {
- // 上面对 nums 的元素加过 10000, 此处要还原
- temp2[index++] = i-10000;
- }
- }
- }
- int sum = 0;
- // 排完序后新的数组 temp2, 依旧取第奇数位元素相加求和
- for (int i=0; i<temp2.length; i += 2) {
- sum += temp2[i];
- }
- return sum;
- }
04 第三种解法
对于第二种解法, 我们还可以优化下, 变得更加简单点. 在记数完成后, 直接对新数组中的数据进行处理.
因为我们只要排在第奇数位的元素, 所以引用一个布尔类型的变量 odd, 当 temp[i]大于 0 的时候, 表示遇到了 nums 中的元素, 拿到 nums 的元素依旧是新数组的索引 i 减去 10000, 加完一次后 odd 变量需要变成 false, 在第 3 次 (奇数次) 进来的时候, 再加上当前元素, 如果当前元素出现了多次的话.
- public int arrayPairSum3(int[] nums) {
- int[] temp = new int[20001];
- for (int i=0; i<nums.length; i++) {
- temp[nums[i]+10000]++;
- }
- int sum = 0;
- boolean odd = true;
- for (int i=0; i<temp.length; i++) {
- while (temp[i]> 0) {
- if (odd) {
- sum += i-10000;
- }
- odd = !odd;
- temp[i]--;
- }
- }
- return sum;
- }
05 小结
算法专题目前已日更超过三个月, 算法题文章 129 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/6a6c65c86429