当前位置 : 首页 » 文章分类 :  开发  »  LeetCode.561.Array Partition I

LeetCode.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 = min(1, 2) + min(3, 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].

解题过程

2n个整数,两两一对,取每对中较小者之和,使和最大。
最大数肯定取不到,想要取到第二大数就只能把第二大和最大的配成一对,剩下的也依次这么考虑,所以只能是从小到大排序然后取每对中的较小者。
所以方法就是递增排序,然后取奇数位数字之和。

package _561_ArrayPartition1;

import java.util.Arrays;

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);//正序排序
        int sum=0;
        for(int i=0; i<nums.length; ){
            sum+=nums[i];
            i=i+2;
        }
        return sum;
    }
}

public class ArrayPartition1 {
    public static void main(String[] args){
        Solution solution = new Solution();
        int[] nums={1,4,3,2};
        System.out.println(solution.arrayPairSum(nums));
    }
}

一次AC,通过这道题还学习了java中Arrays类的使用,java.util.Arrays提供了很多操作数组的方法,以后会经常使用。


GitHub代码


上一篇 java.util.Arrays

下一篇 LeetCode.728.Self Dividing Numbers

阅读
343
阅读预计2分钟
创建日期 2018-01-11
修改日期 2018-01-11
类别
百度推荐