目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:

输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]

示例 2:

输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]

示例 3:

输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]

二、解题思路

题目太难，总之就是遍历所有的组合k=i+j，然后融合两个数组，比较每次res的大小，得到最大的。

三、代码

  

   

    

     

    
    

     

      class Solution1:
     
    
   

    

     

    
    

     
 def maxNumber(self, nums1: list, nums2: list, k: int) -> list:
     
    
   

    

     

    
    

     

       m = len(nums1)
     
    
   

    

     

    
    

     

       n = len(nums2)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       res = [0 for _ in range(k)]
     
    
   

    

     

    
    

     
 for i in range(max(0, k - n), k + 1):
     
    
   

    

     

    
    

     
 if i <= m:
     
    
   

    

     

    
    

     

       arr = self.merge(nums1=self.maxlist(nums1, i),
     
    
   

    

     

    
    

     

       nums2=self.maxlist(nums2, k - i),
     
    
   

    

     

    
    

     

       k=k)
     
    
   

    

     

    
    

     
 if self.compare_same_location_num(arr, 0, res, 0):
     
    
   

    

     

    
    

     

       res = arr
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def maxlist(self, nums, k):
     
    
   

    

     

    
    

     

       n = len(nums)
     
    
   

    

     

    
    

     

       res = [0 for _ in range(k)]
     
    
   

    

     

    
    

     

       j = 0
     
    
   

    

     

    
    

     
 for i in range(n):
     
    
   

    

     

    
    

     
 while n - i + j > k and j > 0 and nums[i] > res[j - 1]:
     
    
   

    

     

    
    

     

       j -= 1
     
    
   

    

     

    
    

     
 if j < k:
     
    
   

    

     

    
    

     

       res[j] = nums[i]
     
    
   

    

     

    
    

     

       j += 1
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def merge(self, nums1, nums2, k):
     
    
   

    

     

    
    

     

       res = [0 for _ in range(k)]
     
    
   

    

     

    
    

     

       i, j = 0, 0
     
    
   

    

     

    
    

     
 for r in range(k):
     
    
   

    

     

    
    

     
 if self.compare_same_location_num(nums1, i, nums2, j):
     
    
   

    

     

    
    

     

       res[r] = nums1[i]
     
    
   

    

     

    
    

     

       i += 1
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     

       res[r] = nums2[j]
     
    
   

    

     

    
    

     

       j += 1
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def compare_same_location_num(self, nums1, i, nums2, j):
     
    
   

    

     

    
    

     
 while i < len(nums1) and j < len(nums2) and nums1[i] == nums2[j]:
     
    
   

    

     

    
    

     

       i += 1
     
    
   

    

     

    
    

     

       j += 1
     
    
   

    

     

    
    

     
 return j == len(nums2) or (i < len(nums1) and nums1[i] > nums2[j])
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      class Solution2:
     
    
   

    

     

    
    

     
 def maxNumber(self, nums1: list, nums2: list, k: int) -> list:
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 # 求出单个数组可以组成i位的最大数组
     
    
   

    

     

    
    

     
 def getMaXArr(nums, i):
     
    
   

    

     

    
    

     
 if not i:
     
    
   

    

     

    
    

     
 return []
     
    
   

    

     

    
    

     
 # pop表示最多可以不要nums里几个数字，要不组成不了i位数字
     
    
   

    

     

    
    

     

       stack, pop = [], len(nums) - i
     
    
   

    

     

    
    

     
 for num in nums:
     
    
   

    

     

    
    

     
 while pop and stack and stack[-1] < num:
     
    
   

    

     

    
    

     

       pop -= 1
     
    
   

    

     

    
    

     

       stack.pop()
     
    
   

    

     

    
    

     

       stack.append(num)
     
    
   

    

     

    
    

     
 return stack[:i]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def merge(tmp1, tmp2):
     
    
   

    

     

    
    

     
 return [max(tmp1, tmp2).pop(0) for _ in range(k)]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       res = [0] * k
     
    
   

    

     

    
    

     
 for i in range(k + 1):
     
    
   

    

     

    
    

     
 if i <= len(nums1) and k - i <= len(nums2):
     
    
   

    

     

    
    

     
 # 取num1的i位, num2的k - i
     
    
   

    

     

    
    

     

       tmp1 = getMaXArr(nums1, i)
     
    
   

    

     

    
    

     

       tmp2 = getMaXArr(nums2, k - i)
     
    
   

    

     

    
    

     
 # 合并
     
    
   

    

     

    
    

     

       tmp = merge(tmp1, tmp2)
     
    
   

    

     

    
    

     
 if res < tmp:
     
    
   

    

     

    
    

     

       res = tmp
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       nums1 = [3, 4, 6, 5]
     
    
   

    

     

    
    

     

       nums2 = [9, 1, 2, 5, 8, 3]
     
    
   

    

     

    
    

     

       k = 5
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       s1 = Solution1()
     
    
   

    

     

    
    

     

       ans1 = s1.maxNumber(nums1, nums2, k)
     
    
   

    

     

    
    

     

       print(ans1)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       s2 = Solution2()
     
    
   

    

     

    
    

     

       ans2 = s2.maxNumber(nums1, nums2, k)
     
    
   

    

     

    
    

     

       print(ans2)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/110470551