O(n) Intuitive Java solution with fully explanation


  • 0
    X

    See the proof it from:https://discuss.leetcode.com/topic/87206/java-solution-sorting-and-rough-proof-of-algorithm
    Ex: For a serious number(6,1,5,2,4,3)
    We have to sort the array and the max outcome will be the following:
    We have to select 1 from(1,2), 3 from(3,4), 5 from(5,6).

    We can use the hash map to do the same effect in O(n) without O(nlogn) sort first.

    1.Store every number in a hash map. We store -10000 on index 0 ~~~ 10000 on index 20001.
    (index of map: adjusted value of a number, value of map: count of the number)
    Ex: map[0] = 100, means -10000 occurs 100 times.

    2.Then we start from the index 0 to index 20001.(Same effect as you sort the array itself).

    3.I first define that left over means whether previous pair is complete or not.
    If not, leftover = true, otherwise.
    We only have to consider four cases:

    0_1493023668086_LeftOver.jpg

    public class Solution {
        public int arrayPairSum(int[] nums) {
            
            int[] arr = new int[20001];
            int lim = 10000;
            
            for (int num: nums)
                arr[num + lim]++;
            
            // leftOver means that there is one alone element in the left
            // thinks it as already choose one for one pair
            // ex: [(2), 2], [(2), 2], (2), leftOver = true;
            boolean leftOver = false;
            int sum = 0;
            for (int i = -10000; i <= 10000; i++) {
                int index = i + lim;
                // even
                if(arr[index] % 2 == 0){
                    if(leftOver) {
                        leftOver = true;
                        sum += (arr[index] / 2) * i;
    
                    }
                    else {
                        leftOver = false;
                        sum += (arr[index] / 2) * i;
    
                    }
                }
                // odd
                else if(arr[index] % 2 == 1){
                    if(leftOver) {
                        leftOver = false;
                        sum += (arr[index] / 2) * i;
    
                    }
                    else {
                        leftOver = true;
                        sum += ((arr[index] + 1) / 2) * i;
                    }
                }
            }
            
            return sum;
        }
    }
    

Log in to reply
 

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