12ms Java Solution (beats 99.78%)


  • -1
    S

    The solution is inspired by @dietpepsi and @chellya based on the following posts:
    [1]: https://discuss.leetcode.com/topic/32272/share-my-greedy-solution
    [2]: https://discuss.leetcode.com/topic/36805/c-16ms-fastest-beats-97

    I used optimization introduced in [2] and the merge method introduced in [1].

    To summarize:

    1. We can find the max number with length X (named maxNumLenX) from an array nums using stack method. [1][2]
    2. Based on maxNumLenX, we can find max numbers with length of X-1, X-2, ..., 1. [2].
    3. Based on 1. and 2., we can solve the problem like this:
      a. Find maxNum2 with max possible length from nums2.
      b. Find all max numbers with less length to the min possible length.
      c. Try maxNum1 with every possible length, starting from the max possible length; Directly fetch the corresponding maxNum2 (maxNum1.length + maxNum2.length ==k), merge them and generate the results.
      d. When generating maxNum1 with length X in the loop, we can generate it from maxNum1 with length X+1.

    Here is the code (it is long, but clear I believe):

    public class Solution {
        public int[] maxNumber(int[] nums1, int[] nums2, int k) {
    		if (k==0) return new int[k];
    		if (nums1.length==0){
    			return getMaxNumberFromNums(nums2,k);
    		}
    		if (nums2.length==0){
    			return getMaxNumberFromNums(nums1,k);
    		}
    
            // Generates the max number of nums2 with the max possible length.
    		int[] maxNum2 = getMaxNumberFromNums(nums2,Math.min(nums2.length,k));
    		
    		// Generates the max number of nums2 of each possible length.
    		Deque<int[]> maxNums2 = getMaxNumsForAllLenth(maxNum2,Math.max(k-nums1.length, 0));
    		
    		
    		int[] maxNum1 = getMaxNumberFromNums(nums1,Math.min(nums1.length,k));
    		int[] res = new int[k];
    		for (int len1 = Math.min(nums1.length,k);len1>=Math.max(k-nums2.length,0);len1--){
    			if (len1 < Math.min(nums1.length,k)){
    				maxNum1 = getMaxNumWithOneLessLen(maxNum1);
    			}
    			maxNum2 = maxNums2.pollFirst();
    			res = getNewMaxNumber(res,maxNum1,maxNum2);
    		}
    		return res;
    	}
        
        // Get max number with length of maxNumLen from nums.
    	public int[] getMaxNumberFromNums(int[] nums, int maxNumLen){
    		int[] maxNum = new int[maxNumLen];
    		int len = nums.length;
    		int end = 0;
    		for (int i=0;i<len;i++){
    			while (end >= 1 && maxNum[end-1] < nums[i] && len - i > maxNumLen - end){
    				end--;
    			}
    			if (end < maxNumLen) maxNum[end++] = nums[i];
    		}
    		return maxNum;
    	}
    
        // Get max numbers with length of maxNum.length, maxNum.length-1, ..., minLen, based on maxNum.
    	public Deque<int[]> getMaxNumsForAllLenth(int[] maxNum, int minLen){
    		Deque<int[]> maxNums = new LinkedList<int[]>();
    		maxNums.add(maxNum);
    		while (maxNum.length>minLen){
    			int[] nextNum = getMaxNumWithOneLessLen(maxNum);
    			maxNums.addFirst(nextNum);
    			maxNum = nextNum;
    		}
    		return maxNums;
    	}
    
        // Get the max number with length of  maxNum.length-1 from maxNum.
    	public int[] getMaxNumWithOneLessLen(int[] maxNum){
    		int len = maxNum.length, end = 0;
    		int[] nextNum = new int[len-1];
    		boolean deleted = false;
    		for (int i=0;i<len;i++){
    			if (end >= len-1) break;
    			if ((i==len-1 || maxNum[i] >= maxNum[i+1]) || deleted){
    				nextNum[end++] = maxNum[i];				
    			} else {
    				deleted = true;
    			}				
    		}	 
    		return nextNum;
    	}
    
        // Merge part1 and part2 into a new max number, substitute the old one if the new one is larger. 
    	public int[] getNewMaxNumber(int[] maxNum, int[] part1, int[] part2){
    		int[] newNum = new int[maxNum.length];
    		int p1 = 0, p2 = 0, index = 0;
    		boolean newNumLarger = false;
    		while (p1 < part1.length || p2 < part2.length){
    			newNum[index] = (greater(part1,p1,part2,p2)) ? part1[p1++] : part2[p2++];
    			
    			// Early termination, if we find new number is less than the existing one.
    			if (maxNum[index] > newNum[index] && !newNumLarger){
    				return maxNum;
    			} else if (maxNum[index] < newNum[index]){
    				newNumLarger = true;
    			}
    			index++;
    		}
    		return newNum;
    	}
    	
    	// This is function is important. When merging two parts into the max number, we need address the case part1[p1] == part2[p2].
    	public boolean greater(int[] part1, int p1, int[] part2, int p2){
    	    while (p1<part1.length && p2<part2.length && part1[p1]==part2[p2]){
    	        p1++;
    	        p2++;
    	    }
    	    
    	    return p2==part2.length || (p1 < part1.length && part1[p1] > part2[p2]);
    	}
    }

Log in to reply
 

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