(java)leetcode561 数组拆分1(Array Partition 1)

题目描述:

给定长度为 2n 的数组, 你的任务是将这些数分成 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。

示例:

输入: [1,4,3,2]

输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).

提示:

  • n 是正整数,范围在 [1, 10000].
  • 数组中的元素范围在 [-10000, 10000].

解题思路:

这一题实现起来并不难,主要是要知道再什么样的情况下这个和才是最大的,然后就知道要怎么去解决。首先是将数组分成N对,然后找出每一对中的最小值,使得这些最小值加起来最大。我们要做的就是使这些最小值尽量的大,那这就要求每一对的两个数之间的差值尽可能的小。到这里我们就明白了这题要怎么做了,其实就是一个数组的排序,然后将没两个挨在一起的数分为一组,取出最小值求和,若是从小到大排序,那就是求出下表为偶数的值的和。

我这里采用的Java 数组自带的排序方法,如果想要提高算法效率,可以自己重新写一个排序算法,可以参考我的另一篇博文《十大经典排序算法(动图演示)》

代码实现(java):

class Solution {
    public int arrayPairSum(int[] nums) {
        int sum=0;
        

        //数组从小到大排序
        Arrays.sort(nums);
        
        for(int i=0;i<nums.length;i=i+2){
            sum+=nums[i];
        }
        return sum;
    }
}

本人才疏学浅,若文中有错误或者有更好的方法,欢迎再评论区中指出,共同进步。

猜你喜欢