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:

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 
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].

 Idea 1. As the sum of the array is fixed, sum = Sa + Sb = 2*Sa + Sb - Sa, to get the maximum sum of smaller group, we want to minimize the diffence of the sum of these two groups, hence to pair the numbers closest to each other in sorted order.

Time complexity: O(NlgN)

Space complexity: O(1)

 1 class Solution {
 2     public int arrayPairSum(int[] nums) {
 3         Arrays.sort(nums);
 4         int result = 0;
 5         for(int i = 0; i < nums.length; i += 2) {
 6             result += nums[i];
 7         }
 8         
 9         return result;
10     }
11 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄