Array Partition I–LeetCode#561

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.
(给一个数量为2n的整数数组,分成n组,求每组最小值的和(尽可能大))

Example:

Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

思路:将数组递增排序,最大的和是第1,3,5,7…n-1数的和.

public class ArrayPartitionI {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int result = 0;
        for (int i=0;i<nums.length;i+=2){
            result += nums[i];
        }
        return result;
    }
    public static void main(String[] args) {
        ArrayPartitionI arrayPartitionI=new ArrayPartitionI();
        int[] nums={1,1,1,1};
        System.out.println(arrayPartitionI.arrayPairSum(nums));
    }
}
文章已创建 112

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部