share my java solution! beat 90%!


  • 6
    C
    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+=(i-10000);
                     }
                     p++;
                     hash[i]--;
                 }
             }
             return sum;
        }
    }
    

  • 0
    C

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


  • 0
    L

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


  • 4
    P

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


  • 0
    M

    It's a wonderful solution, thanks for sharing!


Log in to reply
 

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