Skip to content

Latest commit

 

History

History
158 lines (100 loc) · 3.88 KB

0321._Create_Maximum_Number.md

File metadata and controls

158 lines (100 loc) · 3.88 KB

321. Create Maximum Number

难度: Hard

刷题内容

原题连接

内容描述

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]

解题方案

思路 1 - 时间复杂度: O((m+n)^2 * max(m,n))- 空间复杂度: O(m+n)******

  • 一共k位digit，我们可以先确定从nums1里面取i位，那么从nums2肯定就是取k-i位
  • 然后我们确定了从nums1里面取i位的话，就可以算出所能取得的长度为i的最大子序列lis1，相应的也可以算出从nums2取得的长度为k-i的最大子序列lis2
  • 然后我们用双指针依次从lis1和lis2中取较大的那个数就可以了，不停更新res

Note：

  1. i至少需要k - len(nums2)，否则digit不够, 但是如果k - len(nums2)小于0的话，i还是要从0开始取
  2. i最多取到k，但是因为num1也有长度限制，所以如果k > len(nums1)的时候，i最多取len(nums1)

参考

  1. 智慧巅峰
  2. 细语呢喃

假设num1 和 nums2的长度分别为m和n，因为这里k最大可以为m+n，getLis函数的时间复杂度为O(N)，max(lis1, lis2).pop(0)的时间复杂度为O(N)（因为需要重新排列），

所以总的时间复杂度为O([m+n] * [m + n + k * max(m,n)])，也可以直接看为O((m+n)^2 * max(m,n))

beats 46.87%

class Solution:
    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[int]
        """
        def getLis(nums, k):
            res, n = [], len(nums)
            for i in range(n):
                while res and len(res) + n - i > k and res[-1] < nums[i]:
                    res.pop()
                if len(res) < k:
                    res.append(nums[i])
            return res
        
        res = [0] * k
        for i in range(max(0, k-len(nums2)), min(k, len(nums1)) + 1):
            lis1 = getLis(nums1, i)
            lis2 = getLis(nums2, k-i)
            res = max(res, [max(lis1, lis2).pop(0) for _ in range(k)])
        return res

思路 2 - 时间复杂度: O((m+n)^2)- 空间复杂度: O(m+n)******

我们可以省去max(lis1, lis2).pop(0)重新排列的时间，用deque就可以了

此时总的时间复杂度为O([m+n] * [m + n + (m+n) + k])，也可以直接看为O((m+n)^2)

beats 50%

class Solution:
    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[int]
        """
        def getLis(nums, k):
            res, n = [], len(nums)
            for i in range(n):
                while res and len(res) + n - i > k and res[-1] < nums[i]:
                    res.pop()
                if len(res) < k:
                    res.append(nums[i])
            return res
        
        res = [0] * k
        for i in range(max(0, k-len(nums2)), min(k, len(nums1)) + 1):
            lis1 = getLis(nums1, i)
            lis2 = getLis(nums2, k-i)
            lis1, lis2 = list(map(collections.deque, [lis1, lis2]))
            res = max(res, [max(lis1, lis2).popleft() for _ in range(k)])
        return res