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]
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]
In order to solve this problem, we should firstly build int[] maxNumber(int[] num, int k) function, which returns maximum int array from num[] with length k.
For example:
num[] = {9, 2, 5, 3, 8}, k = 5, return {9, 2, 5, 3, 8}
num[] = {9, 2, 5, 3, 8}, k = 4, return {9, 5, 3, 8}
num[] = {9, 2, 5, 3, 8}, k = 3, return {9, 5, 8}
num[] = {9, 2, 5, 3, 8}, k = 2, return {9, 8}
In order to achieve this function, we use a stack. Basic idea is that it pops stack top if next element is greater than stack top, and number of rest element is enough to fill k elements in stack.
We still need to create a compare function. int compare(int[] num1, int i, int[] num2, int j)
It returns positive if num1{i, i+1,…} is “greater” than num2{j, j+1, …}.
It returns negative if num1{i, i+1,…} is “less” than num2{j, j+1, …}.
It returns negative if num1{i, i+1,…} is “equal” to num2{j, j+1, …}.
For example,
num1 = {9, 2, 5, 8, 3}, i = 1, int[] num2= {5, 6, 6}, j = 0. Then we know 2583 is less than 566. So return negative number.
num1 = {9, 2, 5, 8, 3}, i = 2, int[] num2= {5, 6, 6}, j = 0. Then we know 583 is greater than 566. So return positive number.
Then the final solution is that we use this maxNumber function build i elements array from nums1 and k – i elements from nums2(i belongs to [0,…,k]). Then we merge them. When we merge, we should use compare to decide where the next element from.
check my code on github: link