561. Array Partition I
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1:
Input: [1,4,3,2] Output: 4 Explanation: n is 2, and the maximum sum of pairs is 4.
Note:
- n is a positive integer, which is in the range of [1, 10000].
- All the integers in the array will be in the range of [-10000, 10000].
思路:
[1,4,3,2]可以分为以下几种情况:[(1,2), (3,4)]、[(1,4), (2,3)]、[(1,3), (2,4)],其中,第一种情况sum最小(1+3 = 4)
对于[(1,2), (3,4)]:
如果把3和1替换,则为[(2,3), (1,4)],此时的sum = 2 + 1 = 3 < 4
如果把3和2替换,则为[(1,3), (2,4)],此时的sum = 1 + 2 = 3 < 4
如果把4和1替换,则为[(2,4), (1,3)],此时的sum = 2 + 1 = 3 < 4
如果把4和2替换,则为[(1,4), (2,3)],此时的sum = 1 + 2 = 3 < 4
以上说明,只要有替换发生,sum值就小于4。因此,数字之间不能替换,要想sum值最大,就必须保持原位,即按顺序递增排列。
当然,以上只是找规律罢了。还需要严谨地证明,下面的证明来自Discuss里的大神。
现假设一个pair表示为:(ai, bi),并且对于任意的 i,有ai < bi。则:
Sum = min(a1, b1) + min(a2, b2) + min(a3, b3) + … + min(an, bn)
= a1 + a2 + a3 + … + an
令 Sa = a1 + b1 + a2 + b2 + a3 + b3 + … + an + bn
Sd = (b1 - a1) + (b2 - a2) + (b3 - a3) + … + (bn - an)
= d1 + d2 + d3 + … + dn ,其中 di = bi - ai
则 Sa = a1 + a1 + d1 + a2 + a2 + d2 + a3 + a3 + d3 + … + an + an + dn
= 2*Sum + Sd
则 Sum = ( Sa - Sd ) / 2
由于Sa是数组元素的累加和,是一个定值,因此求Sum的最大值,就是求Sd的最小值。求Sd的最小值,可以参考下图,在下图的三种情况中,只有第一种的Sd是最小的。说明按照递增顺序的Sd是最小的,这和刚刚找到的规律一致。
程序很好写了,排序,然后遍历即可
import java.util.Arrays;
public class Solution {
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;
}
}
上一篇:
算法