Java greedy algorithm with merge sort source code and proof


  • 0
    T
    public class Solution {
        //Use greedy algorithm. Sort the given array in ascending order and group 2 integers from beginning to end.
        //Poof: If there exists any reverse in optimal solution: (ai,bj), (aj, bi) (i<j);
        //Then the sum of those two pairs is ai+bi. The orginal is ai+aj, which is bigger than ai+bi (bi<aj). Contradiction.
        public int arrayPairSum(int[] nums) {
            mergeSort(nums);
            int sum = 0;
            for(int i = 0; i < nums.length; i=i+2){
                sum += nums[i];
            }
            return sum;
        }
        
        public void mergeSort(int[] nums) {
    		if(nums.length>1){
    			//merge
    			int p = nums.length/2;
    			int[] arr1 = new int[p];
    			int[] arr2 = new int[nums.length-p];
    			for (int i = 0; i < p; i++) {
    				arr1[i] = nums[i];
    				arr1[i] = nums[i];
    			}
    			for (int i = p; i < nums.length; i++) {
    				arr2[i-p]=nums[i];
    				arr2[i-p]=nums[i];
    				
    			}
    			mergeSort(arr1);
    			mergeSort(arr2);
    			//sort
    			int m = 0,n=0;
    			for (int i = 0; i < nums.length; i++) {
    				if (m<arr1.length&&n<arr2.length&&arr1[m]<arr2[n]) {
    					nums[i]=arr1[m];
    					nums[i]=arr1[m];
    					m++;
    				}
    				else if (m<arr1.length&&n<arr2.length&&arr1[m]>=arr2[n]) {
    					nums[i]=arr2[n];
    					nums[i]=arr2[n];
    					n++;
    				}
    				else if (m>=arr1.length&&n<=arr2.length) {
    					nums[i]=arr2[n];
    					nums[i]=arr2[n];
    					n++;
    				}
    				else if (n>=arr2.length&&m<=arr1.length){
    					nums[i]=arr1[m];
    					nums[i]=arr1[m];
    					m++;
    				}
    			}
    			return;
    		}
    		else {
    			return;
    		}
    	}
    }
    

Log in to reply
 

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