这是悦乐书的第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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论