首页 > 编程语言 > 详细

【LeetCode】数组-6(561)-Array Partition I(比较抽象的题目)

时间:2017-08-19 10:44:18      阅读:299      评论:0      收藏:0      [点我收藏+]

题目描述:两句话发人深思啊。。。。

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.

技术分享

感觉题目的大致意思就是把数组分成很多个二元数组,对它们以求最小值的方式求和,使得和最大。

思路:

最开始的思路,现在还不知道对不对,就是先排序数组,使用一个指针向后遍历,求最小并求和。??【注意】指针每次累加 2 

【正确代码】 一次写对~

 1 class Solution {
 2     public int arrayPairSum(int[] nums) {
 3         if (nums.length % 2 != 0 || nums == null) {
 4             return -1;
 5         }
 6         Arrays.sort(nums);
 7         int maxSum = 0;
 8         for (int i = 0; i < nums.length - 1; i += 2) {
 9             maxSum += Math.min(nums[i], nums[i + 1]);
10         }
11         return maxSum;
12     }
13 }

时间复杂度:O(n*logn)

空间复杂度:O(n*logn)

【LeetCode】数组-6(561)-Array Partition I(比较抽象的题目)

原文:http://www.cnblogs.com/StoneLuo/p/7395580.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!