An Accepted Python Solution


  • 5

    This problem could be divided into 2 sub-problems:

    1. function getMax(nums, t):

    get t numbers from list nums to form one single maximized sub-list, with relative orders preserved

    1. function merge(nums1, nums2):

    merge nums1 and nums2 to form one single maximized list, with relative orders preserved

    The final result could be solved by enumerate the length of sub-list nums1 and nums2, and record the max merged list.

    Python Code:

    class Solution(object):
        def maxNumber(self, nums1, nums2, k):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :type k: int
            :rtype: List[int]
            """
            def getMax(nums, t):
                ans = []
                size = len(nums)
                for x in range(size):
                    while ans and len(ans) + size - x > t and ans[-1] < nums[x]:
                        ans.pop()
                    if len(ans) < t:
                        ans += nums[x],
                return ans
    
            def merge(nums1, nums2):
                ans = []
                while nums1 or nums2:
                    if nums1 > nums2:
                        ans += nums1[0],
                        nums1 = nums1[1:]
                    else:
                        ans += nums2[0],
                        nums2 = nums2[1:]
                return ans
            
            len1, len2 = len(nums1), len(nums2)
            res = []
            for x in range(max(0, k - len2), min(k, len1) + 1):
                tmp = merge(getMax(nums1, x), getMax(nums2, k - x))
                res = max(tmp, res)
            return res
    

    Ref: http://bookshadow.com/weblog/2015/12/24/leetcode-create-maximum-number/


  • 0
    S

    much more concise than mine.


  • 0
    L

    @在线疯狂 said in An Accepted Python Solution:

    if nums1 > nums2:

    Wouldn't that be O(n) operation? Making your merge function O(n^2)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.