数组拆分 I

发表于 | 分类于 |
字数统计: 379 | 阅读时长 ≈ 1

源题目

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

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

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

提示:

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

解题思路

求每对数中最小值之和为最大，则只需要在分割成不同对时，尽量让每对中最小值对最大值的影响最小，比如：

数组： [1,4,3,2]

成对分隔，按照（1,2），（3,4）的方式分隔，每次求最小值时得到的值是较大的，这样总和也就是最大的
由上分析可得，先将数组排序，排序后在依次取相邻两个数的最小值求和，则得到所需结果。

源码

1）使用Java排序算法:leetcode可通过

1
2
3
4
5
6
7
8
9
10
class Solution {  
       public int arrayPairSum(int[] nums) {
           Arrays.sort(nums);
           int result = 0;
           for(int i=0; i < nums.length; i=i+2){
           result = result + nums[i];
           }
       return result;
       } 
   }

2）冒泡排序：leetcode提示超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution{
    public int arrayPairSum2(int[] nums){
        int result = 0;
        //自己写排序算法
        for(int i = 0; i < nums.length-1; i++){
            for(int j = i+1; j < nums.length ; j++){
                if(nums[i]>nums[j]){
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        for(int i = 0; i < nums.length ;i = i+2){
            result += nums[i];
        }
        return result;
    }
}

完整源码

投食