Sort with O(nlogn) and rough proof


  • 0
    Y

    To make the sum of min(ai, bi) the largest, we can put the two integers with the smallest difference in a pair and we will get the biggest sum.

    To prove it, we can give an example, c0, c1, ..., ci, ci+1,..c2n-1 in ascending order. we swap any ci (i != 2n -2 && i!= 2n - 1) with c2n-1 and we will get two new pairs:(ci, c2n-1) and (cj, c2n-2). Their mins are ci and cj respectively. The original pairs' mins are c2n-2 and ci(or cj). We can see c2n-2 + ci(or cj) > ci + cj.
    For all other pair combinations, they are the result after some number of swapping. So we can prove the original pair combinations are the largest one.

    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;
        }
    }
    

Log in to reply
 

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