public class Solution {
public int arrayPairSum(int[] nums) {
int[] hash=new int[20001];
for(int ele:nums){
hash[ele+10000]++;
}
int sum=0;
int p=0;
for(int i=0;i<20001;i++){
if(hash[i]==0) continue;
while(hash[i]!=0){
if(p%2==0){
sum+=(i10000);
}
p++;
hash[i];
}
}
return sum;
}
}
share my java solution! beat 90%!

@cuiqingli1612 Good idea to separate all possibilities into an array
hash
and usewhile (hash[i] != 0)
instead ofif
to tackle duplicates.

@cuiqingli1612 could you pleas explain this a little bit. I cannot understand your wonderful algorithm.

@LucianoKlein Basically he first runs through all nums once and keep record of found digit in hash. So, if the number is found twice then hash[number+10000] = 2 . (have to plus 10000 here because index start at 0 but num could be 10000)
Then he runs through that hash [10000,10000], skip number that does not in the list ( if(hash[i]==0) ). Using this approach we are sure that the lesser number would be processed first.
p here act like a toggle button. You can think of it like a switch. The concept is to pick minimum, skip next minimum, pick next minimum, skip next....