Python solution, 172ms, beats 100%


  • 0
    J
    import math
    
    class RMQ(object):
        def __init__(self, nums):
            self.nums = nums
            n = len(nums)
            if n:
                d = int(math.log(n, 2)) + 1;
                self.table = [[-1 for _ in range(n)] for _ in range(d)]
                for j in range(n):
                    self.table[0][j] = j;
                for i in range(1, d):
                    for j in range(n - (1 << i) + 1):
                        i1 = self.table[i-1][j]
                        i2 = self.table[i-1][j+(1<<(i-1))]
                        if nums[i1] >= nums[i2]:
                            self.table[i][j] = i1
                        else:
                            self.table[i][j] = i2
    
        def get(self, left, right):
            if right < left:
                return -1
            l = right - left + 1
            d = int(math.log(l, 2))
            i1 = self.table[d][left]
            i2 = self.table[d][right+1-(1<<d)]
            if self.nums[i1] >= self.nums[i2]:
                return i1
            return i2
    
    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)
            rmq1, rmq2 = RMQ(nums1), RMQ(nums2)
            
            start_positions = {0: 0}
            
            res = []
            while k:
                max_digit = 0
                new_start_positions = {}
                for s1, s2 in start_positions.items():
                    e1 = n - max(1, k - (m - s2))
                    e2 = m - max(1, k - (n - s1))
        
                    if s1 < n and s2 < m:
                        i1 = rmq1.get(s1, e1)
                        i2 = rmq2.get(s2, e2)
                        if nums1[i1] > nums2[i2]:
                            if nums1[i1] >= max_digit:
                                if nums1[i1] > max_digit:
                                    max_digit = nums1[i1]
                                    new_start_positions = {}
                                new_start_positions[i1 + 1] = s2
                        elif nums1[i1] < nums2[i2]:
                            if nums2[i2] >= max_digit:
                                if nums2[i2] > max_digit:
                                    max_digit = nums2[i2]
                                    new_start_positions = {}
                                new_start_positions[s1] = i2 + 1
                        else:
                            if nums1[i1] >= max_digit:
                                if nums1[i1] > max_digit:
                                    max_digit = nums1[i1]
                                    new_start_positions = {}
                                new_start_positions[i1 + 1] = s2
                                new_start_positions[s1] = i2 + 1
                    elif s1 < n:
                        i = rmq1.get(s1, e1)
                        if nums1[i] >= max_digit:
                            if nums1[i] > max_digit:
                                max_digit = nums1[i]
                                new_start_positions = {}
                            new_start_positions[i + 1] = s2
                    else:
                        i = rmq2.get(s2, e2)
                        if nums2[i] >= max_digit:
                            if nums2[i] > max_digit:
                                max_digit = nums2[i]
                                new_start_positions = {}
                            new_start_positions[s1] = i + 1
                res.append(max_digit)
                start_positions = new_start_positions
                k -= 1
            return res
    

Log in to reply
 

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