JAVA greedy & DP solution 17ms


  • 0
    D

    using dp/greedy to get all possible combination for both nums1 and nums2 then compare all the merge result to find the best one

    public class Solution {
        public int[] maxNumber(int[] nums1, int[] nums2, int k) {
            int maxReach1 = Math.min(nums1.length, k), maxReach2 = Math.min(nums2.length, k);
            List<int[]> dpNums1 = new ArrayList<int[]>(maxReach1+1), dpNums2 = new ArrayList<int[]>(maxReach2+1);
            int[] empty = new int[0];
            dpNums1.add(empty);
            dpNums2.add(empty);
            for (int i=1; i<=maxReach1; i++) dpNums1.add(getNext(nums1, dpNums1.get(i-1)));
            for (int i=1; i<=maxReach2; i++) dpNums2.add(getNext(nums2, dpNums2.get(i-1)));
            int x=maxReach1, y=k-x;
            int[] result = new int[k];
            do {
                tryNextMerge(result, nums1, nums2, dpNums1.get(x), dpNums2.get(y));
            } while (x-->0 && y++<maxReach2);
            
            return result;
        }
        private int[] getNext(int[] nums, int[] prev) {
            int position=prev.length, right = nums.length;
            while(position>=0) {
                int left = position>0? prev[position-1]+1 : 0;
                if (left<right) {
                    int next = left;
                    for (int i=left+1; i<right; i++) if (nums[i]>nums[next]) next = i;
                    int[] result = new int[prev.length+1];
                    for (int i=0; i<position; i++) result[i]=prev[i];
                    result[position]=next;
                    for (int i=position; i<prev.length;i++) result[i+1]=prev[i];
                    return result;
                }
                right = left-1;
                position--;
            }
            return null; //should not reach here
        }
        private void tryNextMerge(int[] result, int[] nums1, int[] nums2, int[] pos1, int[] pos2) {
            long num = 0;
            int a=0, b=0, c=0, next1= (pos1.length>0)?nums1[pos1[0]]:-1, next2 = (pos2.length>0)?nums2[pos2[0]]:-1;
            boolean isBigger = false;
            while (c<result.length) {
                boolean from1 = false;
                if (next1 > next2) from1=true;
                else if (next1 == next2) {
                    int aa=a, bb=b, temp1 = next1, temp2 = next2;
                    while (temp1 == temp2 && temp1 >= next1) {
                        temp1 = (++aa==pos1.length) ? -1 : nums1[pos1[aa]];
                        temp2 = (++bb==pos2.length) ? -1 : nums2[pos2[bb]];
                    }
                    if (temp1 > temp2) from1 = true;
                }
                if (from1) {
                    if (!isBigger){
                        if (next1>result[c]) isBigger = true;
                        else if (next1<result[c]) return;
                    }
                    result[c++]=next1;
                    next1 = (pos1.length>++a) ? nums1[pos1[a]] : -1;
                } else {
                    if (!isBigger){
                        if (next2>result[c]) isBigger = true;
                        else if (next2<result[c]) return;
                    }
                    result[c++]=next2;
                    next2 = (pos2.length>++b) ? nums2[pos2[b]] : -1;
                }
            }
        }
    }
    

Log in to reply
 

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