[容易] Array Partition I

[容易] 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.

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4)

Note:

  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

[解]

现将数组进行排序,相邻的两个数字为一组,取其中最小的。

Method1
开始手写了快排,但是time out没有通过

Method2
使用 java.util.Arrays.sort() 代替快排,Accepted.

对象实现了Comparable接口后即可使用Arrays.sort