O(n) Java solution without sorting


  • 0
    Y
    public class Solution {
        public int arrayPairSum(int[] nums) {
            int n = nums.length >> 1;
            // Since all the integers in the array "nums" is in the range of [-10000, 10000], using an array "m" 
            // to track how many times each integer in above range appears in "nums". For example, if there 
            // are 3 integers of "10" in "nums", m[10000 + 10] =  3; if there is ONE integer of "-10000", m[0] = 1, etc. 
            int[] m = new int[20001];
            // After below for loop,  m[0] + m[1] + ... + m[20001] = 2n
            for (int num : nums) m[num + 10000] += 1;
            int sum = 0;
            int i = 0;
            // Getting n pairs by visiting "m", which is essentially equivalent to visiting the sorted input array like other sorting approaches.
            while (n-- > 0) {
                // m[i] == 0 means integer "i - 10000" doesn't exist in input array or it has been used up in previous pairs.
                while (m[i] == 0) i++;
                sum += (i - 10000);
                m[i]--;
                while (m[i] == 0) i++;
                m[i]--;
            }
            return sum;
        }
    }
    

  • 0
    L

    @yufyu
    can you give some explanation about you code ?
    i can't understand the function about the while loop here ???


  • 1
    Y

    @longshi Some comments were added in the source. Hopefully they will be helpful.


Log in to reply
 

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