[LeetCode做题记录] 561. 数组拆分 I (EASY)

时间: | 分类: LeetCode做题记录

给定长度为 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].

个人思路,根据观察可发现,当数组按升序排列时,将小的数加起来即为结果。例如arr[1,2,3,4,5,6],则arr[0]+arr[2]+arr[4]...为结果。

个人解答(29ms/89.36%):

    public int arrayPairSum(int[] nums) {
        int result = 0;
        Arrays.sort(nums);
        for (int i = 0; i <nums.length ; i=i+2) {
            result+=nums[i];
        }
        return result;
    }

dalao解法(13ms)(注释是提交者写的):

class Solution {
    //考虑先排序,后按大小累加O(n^2)
    //既然考虑到排序,何不考虑桶排序,Space instead of Time 
    //开一个两万范围的桶
    public int arrayPairSum(int[] nums) {
        int[] hash = new int[20001];
        for (int i = 0; i < nums.length; i++) 
            hash[nums[i] + 10000]++;
        int sum = 0;
        //因为2n一定是偶数,所以从左往右先累加小的,odd用来控制,间隔一个再累加
        boolean odd = true;
        for (int i = 0; i < hash.length; i++) {
            while(hash[i] > 0){
                //从左往右,被累加上的一定是min
                if(odd)
                    sum += i - 10000;
                odd = !odd;
                hash[i]--;                
            }
        }
        return sum;
    }
}

可看到基本原理是差不多,就是把Arrays库内的sort方法换成桶排来减少时间消耗,由于还没学桶排所以暂时无法分析..(其实也没啥好分析的


LeetCode



白咲美绘瑠's blog