share my java solution! beat 90%!


  • 5
    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.


  • 2
    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....


Log in to reply
 

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