561. Array Partition I

发表于 2018-03-27 分类于 leetcode

题目

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.

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

算法思想

这道题一开始完全没有思路，看了讨论之后发现需要对所有数据进行排序，然后两两取最小的数相加之和。

心想，排序还不简单，快排随便来一个。结果看了答案发现大神们都是用hashmap桶排序做的…因为这道题指明了数的范围，所以适用桶排序，最快可以达到常数级的时间复杂度。

实现代码

class Solution {
public:
int arrayPairSum(vector<int>& nums) {

    vector<int> hashtable(20001,0);
    for(int i=0;i<nums.size();i++)
    {
        hashtable[nums[i]+10000]++;
    }
    int sum=0, count=0, i=0;
    while(count<nums.size())
    {
        if(hashtable[i]==0){i++;}
        else {
                if (count%2==0)
                sum+=i-10000;
                hashtable[i]--;
                count++;
             }
    }
    
    return sum;
    
}        

};

代码主要使用vector建立一个hashtable，注意进行统计的时候hash的值是nums[i]+10000.
然后主要实现对相邻数的计数，这里采用了一个count，当count值为偶数的时候加入sum。
每次加完一个数之后，hashtable[i]–，直到0，指针指向下一个桶。