欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

561. Array Partition I

程序员文章站 2022-07-16 08:02:40
...

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:

  1. n is a positive integer, which is in the range of [1, 10000].
  2. 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是最小的,这和刚刚找到的规律一致。

561. Array Partition I

程序很好写了,排序,然后遍历即可

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;
    }
}

上一篇: 算法

下一篇: 561. Array Partition I