LeetCode561. 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.

Example 1:

1
2
3
4
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].

Hint:

  1. Obviously, brute force won’t help here. Think of something else, take some example like 1,2,3,4.

  2. How will you make pairs to get the result? There must be some pattern.

  3. Did you observe that- Minimum element gets add into the result in sacrifice of maximum element.
  4. Still won’t able to find pairs? Sort the array and try to find the pattern.

sort

my code in cpp

1
2
3
4
5
6
7
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ret = 0;
for (int i=0;i<nums.size();i+=2)
ret += nums[i];
return ret;
}

总结

未命名2

  1. 根据数学证明,这题就转化为在数组中找到每组差距之和最小的分组,那么就想到了排序。
Thanks for Support.