Java solution and straightforward explanation


  • 1
    H

    Assume there is an array:
    a1 < a2 < a3 < a4 ...... < a2n
    sum = ?

    As we all known, a1 = min(a1, ai) (1 < i <= 2n).
    So the sum which we want to figure out must include the smallest number a1. When we remove a1 from the given array, which number do you want to killed at the same time? As far as I see, the best answer is a2.

    a3 < a4 < a5 < a6.... < a2n
    sum = a1 + ?

    Now, a3 is the smallest number of array!
    I believe you have already know all story here.

    a5 < a6 < a7 < ... < a2n
    sum = a1 + a3 + ?

    ...

    sum = a1 + a3 + .... + a(2n - 1)

    My first solution:

    public class Solution {
        public int arrayPairSum(int[] nums) {
            Arrays.sort(nums);
            int sum = 0;
            for (int i = 0; i < nums.length; i += 2) {
                sum += nums[i];
            }
            return sum;
        }
    }
    

    Since we know the range of array's integers, bucket sort is a faster sort algorithm.

    public class Solution {
        public int arrayPairSum(int[] nums) {
            int[] array = new int[20001];
            for (int i = 0; i < nums.length; i++) {
                array[nums[i] + 10000]++;
            }
            int sum = 0;
            boolean smaller = true;
            for (int i = 0; i < array.length;) {
                if (array[i] > 0) {
                    if (smaller) {
                        sum += i - 10000;
                    }
                    smaller = !smaller;
                    array[i]--;
                } else {
                    i++;
                }
            }
            return sum;
        }
    }
    

Log in to reply
 

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