# c++ code O(n),beats 100%

• ``````class Solution {
public:
int arrayPairSum(vector<int>& nums) {
vector<int> hashtable(20001,0);
for(size_t i=0;i<nums.size();i++)
{
hashtable[nums[i]+10000]++;
}
int ret=0;
int flag=0;
for(size_t i=0;i<20001;){
if((hashtable[i]>0)&&(flag==0)){
ret=ret+i-10000;
flag=1;
hashtable[i]--;
}else if((hashtable[i]>0)&&(flag==1)){
hashtable[i]--;
flag=0;
}else i++;
}
return ret;
}
};
``````

with the range of numbers,it is easy to using vector,and if we don't know the range of numbers,maybe using STL multiset,but using multiset is O(nlogn).

• a little bit of improvement...

``````class Solution {
public:
int arrayPairSum(vector<int>& nums) {
int ret = 0;
bool flag = true;
array<int, 20001> hashtable{ 0 };
for (const auto n : nums) {
++hashtable[n + 10000];
}
for (int i = 0; i < 20001;) {
if (hashtable[i] > 0) {
if (flag) {
flag = false;
ret += (i - 10000);
--hashtable[i];
} else  {
flag = true;
--hashtable[i];
}
} else
++i;
}
return ret;
}
};
``````

• @i_square it is a good habit to use bool flag,ty

• nice solution

• Thank you,I use sort originally. Your thinking make it quicker.

``````class Solution {
public:
int arrayPairSum(vector<int>& nums) {
vector<short> hash(20001);
int sum=0;
for (auto e:nums) {++hash[e+10000];}
for (int i=0,j=1; i<20001; ) {
if (hash[i]>0) {
if (j==1) {sum+=i-10000;}
j^=1;
if (--hash[i]==0) ++i;
} else {++i;}
}
return sum;
}
};
``````

• a little improvement

``````int arrayPairSum(vector<int>& nums) {
vector<int> map(20001,0);
for(auto n:nums)map[n+10000]++;
int result=0,remain=0;
for(int x=0;x<=20000;x++)
{

result+=(x-10000)*((map[x]+1-remain)/2);
remain=(remain+map[x])%2;
}

return result;
}``````

• Could someone explain what the code is doing? I'm having a hard time following this one.

• @jejeirs Bucket sort，you can google it.

• @jejeirs Idea: Bucket Sort can sort an integer array in linear time when we know the scope of all the integers.

• is this hashtable an unordered_map?

• @needforspeed `vector<int> hashtable(20001,0);` I think it is a `vector` of `int`.

• good job.
as a newbie,I have learned a lot from bool true

• Keep counting so that you do not need to loop to the end of the buckets if not necessary

``````class Solution {
public:
int arrayPairSum(vector<int>& nums) {
// Using bucket sort since we know the range of the integers are from -10000 - 10000

vector<int> buckets(200001, 0);
for(int i:nums) {++buckets[i+10000];}

int sum = 0, count = 0, i = 0;
while(count < nums.size()) {
if(buckets[i]==0) {
i++;
}
else {
if(count%2==0)
sum += (i-10000);
--buckets[i];
++count;
}
}
return sum;
}
};
``````

• @morrischen2008 That's a nice addition to the solution! thanks.

• Nice solution. Here's a C version:

``````int arrayPairSum(int* nums, int numsSize) {
bool flag = true;
int ret = 0;
int hashtable[20001] = {0};
for (int i = 0; i < numsSize; i++) {
hashtable[nums[i] + 10000]++;
}
for (int i = 0, count = 0; i < 20001, count < numsSize / 2; ) {
if (hashtable[i] > 0) {
if (flag) {
ret += i - 10000;
count++;
}
flag = !flag;
if (--hashtable[i] == 0) {
i++;
}
} else {
i++;
}
}
return ret;
}
``````

• @lun0522 said in c++ code O(n),beats 100%:

nums

Could you please give me the details of the algorithm? I solved in nlogn time but this one looks like more efficient. Thank you very much

To make it easier to understand, suppose that all the integers in the array will be in the range of [0, 10000] rather than [-10000, 10000]. We create an array, named `hashtable`, whose capacity should be (10000 - 0) + 1 = 10001. This array is used to keep track of the times that an element appears in the original array.

The key is to use the element itself as the index. For example, we traverse `nums`, if we encounter a `5`, just do `hashtable[5]++;`; if we encounter a '9', do `hashtable[9]++;`, and so on. This is what the first `for` loop used to do.

In the second loop, we traverse `hashtable`. If `hashtable[0] == 2`, which means there are two `0` in `nums`, so the sorted array should start with two `0`; if `hashtable[1] == 3`, there should be three `1` after those two `0`, etc.

Here we set two variables, `flag` and `count`. Since we just have to calculate the sum of min(ai, bi), which is the same to the sum of elements in even-index positions (0, 2, 4, ...) in the sorted array. `flag` labels whether the element is in an even or odd position, and `count` is a sentinel that stops the loop.

Each time we encounter an element, do `--hashtable[i]` to record we have already dealt with it. But `i` should not increase by 1 every time. Say if we have `hashtable[5] == 2`, after we dealt with the first `5`, `i` should keep being `5` so we will encounter the second `5` later. That's why we use:

``````if (--hashtable[i] == 0) {
i++;
}
``````

In the problem, the range of elements is [-10000, 10000], so we have to create an `hashtable` of length 10000 - (-10000) + 1 = 20001; in the first loop, use `hashtable[nums[i] + 10000]++;` instead so that indices would not be negative; in the second loop, use `ret += i - 10000;` to neutralize that 10000 added before.

I think this is clear enough. The time complexity should be O(n). This method is especially useful if we know the range of elements, and the range is not very large (like [INT_MIN, INT_MAX]) (or the space complexity will be huge).

Happy coding!

• class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
int result=0;
for(int i=0;i<nums.size();i=i+2)
{
result+=nums[i];
}
return result;

``````}
``````

};

• a little bit improvement...

``````    int arrayPairSum(vector<int>& nums) {
int res = 0;
vector<int> bucket(20001, 0);
int mini = 10000, maxi = -10000;
for (int i = 0; i < nums.size(); ++i) {
bucket[nums[i] + 10000]++;
mini = min(mini, nums[i]);
maxi = max(maxi, nums[i]);
}
bool odd = false;
for (int i = mini+10000; i <= maxi+10000; ++i) {
res += (i - 10000) * (bucket[i] / 2);
if (!odd && (bucket[i] % 2 == 1)) res += i - 10000;
odd ^= (bucket[i] % 2 == 1);
}
return res;
}
``````

• @morrischen2008 nice implementation, easier to read and understand ! COOL

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.