# divide to three subproblem solution, beat 98%

• subproblem1:
get the largest k numbers when keeping the relative order

subproblem2:
merge two arrays which are from subproblem1.

subproblem3:
compare two arrays.

``````public class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int len1 = nums1.length;
int len2 = nums2.length;
int[] result = new int[k];
if(len1+len2 < k) {
}else if(len1+len2 == k){
result = mergeTwoArrays(nums1, nums2, k);//edge case
}else{
for (int i = 0; i <= k; i++) {
if(i<=len1 && (k-i)<=len2){
int[] maxNumbers1 = maxNumberOfSingleArray(nums1, i);
int[] maxNumbers2 = maxNumberOfSingleArray(nums2, k - i);
int[] maxNumbers = mergeTwoArrays(maxNumbers1, maxNumbers2, k);
if (compareTwoArrays(maxNumbers, 0, result, 0)) result = maxNumbers;
}
}
}
return result;
}

private int[] mergeTwoArrays(int[] nums1, int[] nums2, int k) {
int[] result = new int[k];
int idx1 = 0, idx2 = 0;
int idx = 0;
while(idx < k){
//check the two remain arrays to see which one is larger.
if(compareTwoArrays(nums1, idx1, nums2, idx2)){
result[idx] = nums1[idx1++];
}else{
result[idx] = nums2[idx2++];
}
idx++;
}
return result;
}

//get the largest k numbers when keeping the relative order
private int[] maxNumberOfSingleArray(int[] nums, int k){
int[] result = new int[k];
if(k == 0) return result;

int len = nums.length;
int idx = 0;
for(int i = 0; i < len; i++){
while((len-i-1) + (idx+1) > k && idx>0 && nums[i] > result[idx-1]) idx--;
if(idx < k) result[idx++] = nums[i];
}
return result;
}

//compare two arrays at the "start" index
public boolean compareTwoArrays(int[] nums1, int startIdx1, int[] nums2, int startIdx2) {
int len1 = nums1.length - startIdx1;
if(len1 <= 0) return false;
int len2 = nums2.length - startIdx2;
if(len2 <= 0) return true;
int len = Math.max(len1, len2);
for (int i = 0; i< len; i++) {
int digit1 = startIdx1 + i < nums1.length ? nums1[startIdx1 + i] : 0;
int digit2 = startIdx2 + i < nums2.length ? nums2[startIdx2 + i] : 0;
if(digit1 != digit2){
return digit1 > digit2;
}
}
return true;//equal, choose either one is ok
}
}
``````

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