Create Maximum Number


  • 0
    M
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
            int m = nums1.length;
            int n = nums2.length;
            Comparator<int[]> MyCompare = new Comparator<int[]>(){
                @Override
                public int compare(int[] a, int[] b){
                    int len = a.length;
                    for(int i=0;i<len;i++){
                        if(a[i]!=b[i]){
                            return b[i]-a[i];
                        }
                    }
                    return 0;
                }
            };
            Queue<int[]> queue = new PriorityQueue<int[]>(MyCompare);
            for(int i=Math.max(k-n, 0);i<=Math.min(k,m);i++){
                ArrayList<Integer> val1 = helper(nums1, i);
                ArrayList<Integer> val2 = helper(nums2, k-i);
                int[] res = new int[k];
                res = getMax(val1, val2);
                queue.add(res);
            }
            return queue.poll();
        }
        
        public int[] getMax(ArrayList<Integer> arr1, ArrayList<Integer> arr2){
            int m = arr1.size();
            int n = arr2.size();
            int[] res = new int[m+n];
            int ind1 = 0;
            int ind2 = 0;
            int count=0;
            while(ind1<m && ind2<n){
                if(arr1.get(ind1)>arr2.get(ind2)){
                    res[count] = arr1.get(ind1);
                    count++;
                    ind1++;
                }
                else if(arr1.get(ind1)<arr2.get(ind2)){
                    res[count]=arr2.get(ind2);
                    count++;
                    ind2++;
                }
                else{//arr1.get(ind1)==arr2.get(ind2)
                	int pattern = getPatLen(arr1, arr2, ind1, ind2);
                	if((ind1+pattern)<m && (ind2+pattern)<n){
                		if(arr1.get(ind1+pattern)>arr2.get(ind2+pattern)){
                			res[count]=arr1.get(ind1);
                			count++;
                			ind1++;
                		}
                		else{
                			res[count]=arr2.get(ind2);
                			count++;
                			ind2++;
                		}
                	}
                	else{
                		if((ind1+pattern)<m){
                			res[count] = arr1.get(ind1);
                			count++;
                			ind1++;
                		}
                		else if((ind2+pattern)<n){
                			res[count]=arr2.get(ind2);
                			count++;
                			ind2++;
                		}
                		else{
                			res[count]=arr1.get(ind1);
                			count++;
                			ind1++;
                		}
                	}
                }
            }
            while(ind1<m){
                res[count] = arr1.get(ind1);
                count++;
                ind1++;
            }
            while(ind2<n){
                res[count] = arr2.get(ind2);
                count++;
                ind2++;
            }
            return res;
        }
        
        public ArrayList<Integer> helper(int[] nums, int len){
            ArrayList<Integer> res = new ArrayList<Integer>();
            int start = 0;
            int end = nums.length-len;
            int count =0;
            while(count<len){
                int max = nums[start];
                int ind = start;
                for(int i=start+1;i<=end;i++){
                    if(nums[i]>max){
                        max = nums[i];
                        ind = i;
                    }
                }
                res.add(max);
                start = ind+1;
                end = end+1;
                count++;
            }
            return res;
        }
        
        public int getPatLen(ArrayList<Integer> arr1, ArrayList<Integer> arr2, int ind1, int ind2){
    		int res = 0;
    		while(ind1<arr1.size() && ind2<arr2.size()){
    			if(arr1.get(ind1)!=arr2.get(ind2)){
    				break;
    			}
    			res++;
    			ind1++;
    			ind2++;
    		}
    		return res;
    	}

Log in to reply
 

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