python, 97%, with explanation


  • 0
    Z
    class Solution(object):
        def findMedianSortedArrays(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: float
            """
            l1, l2 = len(nums1), len(nums2)
            l = l1 + l2
            idx, c = l / 2, l % 2
            nums = []
            runner1, runner2 = 0, 0
            while (runner1 + runner2) <= idx:
                if runner1 >= l1:
                    # runner1 has reach the goal, just move runner2
                    nums.append(nums2[runner2])
                    runner2 += 1
                    continue
                if runner2 >= l2:
                    # runner2 has reach the goal, just move runner1
                    nums.append(nums1[runner1])
                    runner1 += 1
                    continue
                n1, n2 = nums1[runner1], nums2[runner2]
                if n1 == n2:
                    # runner1 and runner2 has the same value, we should check their next values
                    if runner1 + 1 == l1:
                        # runner1 has reach the goal, just move runner2
                        nums.append(n2)
                        runner2 += 1
                        continue
                    if runner2 + 1 == l2:
                        # runner2 has reach the goal, just move runner1
                        nums.append(n1)
                        runner1 += 1
                        continue
                    if nums1[runner1 + 1] > nums2[runner2 + 1]:
                        # runner2's next value is smaller, so we move runner2
                        nums.append(n2)
                        runner2 += 1
                    else:
                        # runner1's next value is smaller, so we move runner1
                        nums.append(n1)
                        runner1 += 1
                elif n1 > n2:
                    nums.append(n2)
                    runner2 += 1
                else:
                    nums.append(n1)
                    runner1 += 1
            if c:
                # if c == 1, length of total two arrays is odd
                return nums[idx]
            else:
                return float((nums[idx-1] + nums[idx])) / 2
                    
    

Log in to reply
 

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