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:
Input:
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.

int compare (const void * a, const void * b)
{
    if(*(int *)a < *(int *)b)
        return -1;
    else if(*(int *)a > *(int *)b)
        return 1;
    else 
        return 0;
}

int arrayPairSum(int* nums, int numsSize) 
{
    int sum = 0;
    qsort (nums, numsSize, sizeof(int), compare);
    
    for(int i = 0;i < numsSize;i += 2)
        sum += nums[i];
        
    return sum;
}

将nums中的值映射到下标0-20000,统计整数出现的次数，如果个数大于零并且flag为1则把对应的下标减去1000加到ret中，通过flag我们控制ret的和为原数组中相对顺序出现在奇数的数字的和。

int arrayPairSum(int* nums, int numsSize) 
{
    int hash[20001] = {0};
    int i = 0;
    int flag = 1;
    int ret = 0;
    for(i = 0;i < numsSize;i++)
        hash[nums[i] + 10000] += 1;
    
    for(i = 0;i < 20001;)
    {
        if(hash[i] > 0 && flag)
        {
            ret = ret + i- 10000;
            hash[i] -= 1;
            flag = 0;
        }
        else if(hash[i] > 0 && !flag)
        {
            hash[i]--;
            flag = 1;
        }
        else
            i++;
    }
        
    return ret;
}

另一种相对好理解的实现:

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        int bucket[20001] = {0};
        int sum = 0,cnt = 0,elemt = 0,i = 0;
        //nums中的数据写入桶中
        for(auto it = nums.begin();it != nums.end();it++)
        {
            bucket[*it + 10000]++;
            elemt++;
        }
            
        while(cnt < elemt)
        {
            if(bucket[i] <= 0)
            {
                i++;
            }else {
                if (cnt % 2 ==0)
                    sum += (i -10000);
                //跳过下一个相同元素,如果存在的话(下次判断> 0)
                bucket[i]--;
                cnt++;
            }
        }
        
        return sum;
    }
};