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.
Note: You should try to optimize your time and space complexity.
Example 1:
Input:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
Output:
[9, 8, 6, 5, 3]
Example 2:
Input:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
Output:
[6, 7, 6, 0, 4]
Example 3:
Input:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
Output:
[9, 8, 9]
My code: #I still don't understand what means a list is larger than another list
import numpy as np
class Solution(object):
def maxNumber(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: List[int]
"""
n, m = len(nums1), len(nums2)
ans = [0] * k
for i in range(0, k+1):
j = k - i
if i > n or j > m:
continue
left = self.maxOneNumber(nums1, n, i)
right = self.maxOneNumber(nums2, m, j)
#print(left)
#print(right)
cur = self.merge(collections.deque(left), collections.deque(right))
ans = max(ans, cur)
return ans
def maxOneNumber(self, nums, n, k):
ans = [-1] * k
j = 0
for i in range(n):
while n - i > k - j and j > 0 and ans[j-1] < nums[i]:
j -= 1
if j < k:
ans[j] = nums[i]
j += 1
return ans
def merge(self, nums1, nums2):
ans = []
#print(nums1)
#print(nums2)
while nums1 or nums2:
if nums1 > nums2:
ans.append(nums1.popleft())
else:
ans.append(nums2.popleft())
return ans
def maxNumber1(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: List[int]
"""
#Notes:the problem is a stack problem that pops up to combine a bigger sum value
length1=len(nums1)
length2=len(nums2)
result=[-1]*k
for i in range(k+1):
if i > length1 or k-i > length2:
continue
nums1pop=self.Pick_Value(nums1,i)
nums2pop=self.Pick_Value(nums2,k-i)
print(nums1pop)
print(nums2pop)
tmp_result=self.merge_result(nums1pop,nums2pop)
print(tmp_result)
result=max(result,tmp_result)
return result
def Pick_Value(self,nums,k):
pop_result = [-1] * k
n=len(nums)
j = 0
for i in range(n):
while n - i > k - j and j > 0 and pop_result[j-1] < nums[i]:
j -= 1
if j < k:
pop_result[j] = nums[i]
j += 1
return pop_result
def merge_result(self,nums1,nums2):
nums=[]
length1=len(nums1)
length2=len(nums2)
if length1==0:
return nums2
if length2==0:
return nums1
count=0
i=0
j=0
while count<length1+length2:
if i==length1:
for k in range(j,length2):
nums.append(nums2[k])
count+=1
break
if j==length2:
for k in range(i,length1):
nums.append(nums1[k])
count+=1
break
if nums1[i]>nums2[j]:
nums.append(nums1[i])
i+=1
else:
nums.append(nums2[j])
j+=1
count+=1
return nums
Solution: https://leetcode.com/problems/create-maximum-number/