321. Create Maximum Number
My SubmissionsTotal Accepted: 4905 Total Submissions: 24041 Difficulty: HardGiven two arrays of length m and n with digits 0-9 representing two numbers.
Create the maximum number of length k from digits of the two.
<= m + n
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]
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]
Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
分析k的值有三种情况：（1）k小于nums1的长度，则nums1最多取k个数（2）k大于nums1的长度，则nums1最多取len1个数（3）k小于nums2的长度，则nums1最少取0个数（4）k大于nums2的长度，则nums1最少取k-len2个数
- 因此nums1有可能取 Max（0， k - len2） ---- Min（len1， k） 之间
- 然后针对nums1的所有可能取数的个数情况，进行遍历，此时nums2取k-i个数
