321. Create Maximum Number

Given two arrays of length mand n with digits0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of thek digits. You should try to optimize your time and space complexity.
Example 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]
Example 2:
nums1 =[6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]
Example 3:
nums1 =[3, 9]
nums2 = [8, 9]
k = 3
return[9, 8, 9]

[leetcode 321] Create Maximum Number

给出两个数组，然后从这两个数组中顺序选取k个数，使得这k个数组成的数字最大，这里要求顺序不变，可以将这个问题转为如何对一个数组中顺序选取k个数，使得这k个数组成的数字最大。
那么转化后的该如何解决呢？这里有一个很经典的方法，新建一个大小为k的数组，对原数组中的每个元素遍历，与当前为k的数组的最后一个元素比较，如果大于，就一直替换(条件是原数组后面的元素加上当前k大小的数组的长度大于等于k)，这样就一定可以找到最大的k个数，这种方法应该叫贪心吧。代码如下：

private static int[] maxNumber(int[] nums, int k) {
    int n=nums.length;
    int j=0;
    int []res=new int[k];
    for(int i=0;i<n;i++){
        while (n-i+j>k&&j>0&&nums[i]>res[j-1])j--;
        if(j<k)res[j++]=nums[i];
    }
    return res;
}

那么在一个数组中可以找到k个可以组成最大的数字的数，那两个数组该怎么解决呢，就很简单，如果总共要选取k个数，可以假设从第一个数组中选取i个数，然后从第二个数组中选取k-i个数，这样就变成两个子问题了，然后在将这两个子问题合并，这道题目就解决了。
先来看分解，用一个for循环就可以解决，如下进行分配，使得分配的结果都是合理的：

public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
    int n1=nums1.length,n2=nums2.length;
    int []res=new int[k];
    for(int i=Math.max(k-n2,0);i<=n1&&i<=k;i++){
        int[] ans=merge(maxNumber(nums1,i),maxNumber(nums2,k-i),k);
        if(greater(res,ans))res=ans;
    }
    return res;
}

private static boolean greater(int[] res, int[] ans) {
    for(int i=0;i<res.length;i++){
        if(res[i]==ans[i])continue;
        else if(res[i]>ans[i])return false;
        else return true;
    }
    return false;
}

上面的代码中先是分解，然后合并，找到结果与原结果比较。
那么如何合并呢，这里并不像合并两个有序数组一样简单，还是得考虑很多情况的，比如6,7和6,0,4的合并，结果是6,7,6,0,4，在比如0和0,5,6的合并，结果是0,5,6,0，这里就要求如果两个元素相等，我们需要选取其后面元素大的一个，这部分代码如下：

private static int[] merge(int[] nums1, int[] nums2,int k) {
    int[] ans = new int[k];
    for (int i = 0, j = 0, r = 0; r < k; ++r)
        ans[r] = greater2(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
    return ans;
}

private static boolean greater2(int[] nums1, int i, int[] nums2, int j) {
    while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
        i++;
        j++;
    }
    return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
}