leetcode 561. Array Partition I

作者 qiuzhong 日期 2017-06-12
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.

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:
n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

####解题思路
问题的关键其实在于排序,只要整个数组是有序的，问题就会变得非常简单，假设数组从小到大排列，那么2n位置上的数字相加的和一定是最小的。
然后随手写了个冒泡排序。

for(int i = 0;i<nums.length-1;i++){
        for(int j = 0;j<nums.length-1-i;j++){
            if (nums[j] > nums[j + 1]) {
		int temp = nums[j];
		nums[j] = nums[j + 1];
		nums[j + 1] = temp;
	}
        }
    }

然后开心愉快的提交了代码,WTF!时间超时了,这是在搞事情啊。只能换个高效点的排序算法了。选了插入排序，问题解决。

for( int i=0; i<nums.length-1; i++ ) 
       {	
           for( int j=i+1; j>0; j-- ) 
           {
               if( nums[j-1] <= nums[j] )
                   break;
               int temp = nums[j];
               nums[j] = nums[j-1];
               nums[j-1] = temp;
           }
       }