LC321. Create Maximum Number
Given two arrays of length m and n with digits 0-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 the k 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]
找两个array里最大的k个数，但是要求按照array本身的顺序排序输出，思路是对于两个array，分别取i，j个数，令i + j = k，在所有的结果中取最大的array。
我自己写的时候merge错了几~~百~~次，后来发现如果arr[1]和arr[2]中间的某个数字相等的话，是要先跳到另一个array的…就按照题解改过来了。
public class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
// each time get i numbers from nums1 and j numbers from nums2, i + j = k
// compare each result get the largest one
int len1 = nums1.length, len2 = nums2.length;
int[] ans = new int[k];
for(int i = Math.max(0, k - len2); i <= k && i <= len1; i++){
int[] cur = merge(maxSub(nums1, i), maxSub(nums2, k-i), k);
//if(i == Math.max(0, k - len1)) ans = cur;
if(larger(cur, 0, ans, 0)) ans = cur;
}
return ans;
}
private int[] merge(int[] arr1, int[] arr2, int k){
int[] ans = new int[k];
for (int i = 0, j = 0, r = 0; r < k; ++r)
ans[r] = larger(arr1, i, arr2, j)? arr1[i++] : arr2[j++];
return ans;
} // merge
private int[] maxSub(int[] arr, int k){
int[] res = new int[k];
int n = arr.length;
for(int i = 0, j = 0; i < n; i++){
while(n - i > k - j && j > 0 && res[j-1] < arr[i]) j--; // older number is less, cover it
if(j < k) res[j++] = arr[i]; // find a larger number
}
return res;
} // maxSub
private boolean larger(int[] arr1, int i, int[] arr2, int j){
while (i < arr1.length && j < arr2.length && arr1[i] == arr2[j]) {
i++;
j++;
}
return j == arr2.length || (i < arr1.length && arr1[i] > arr2[j]);
} // larger
}
O()(n+m)^3) worst
后来又看了 细语呢喃的题解, greater函数也可以这样写。
枚举数组长度复杂度O(k)，找出最大子数组O(n)，合并的话O(k^2)
而k最坏是m+n,所以总的复杂度就是O((m+n)^3)
public boolean greater(int[] nums1, int start1, int[] nums2, int start2) { for (; start1 < nums1.length && start2 < nums2.length; start1++, start2++) { if (nums1[start1] > nums2[start2]) return true; if (nums1[start1] < nums2[start2]) return false; } return start1 != nums1.length; }