Median of two Sorted arrays—Heap solution

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Example 1:

The overall run time complexity should be O(log (m+n)) (Disregard this for the purposes of this question)

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Leetcode

Solution

1. The median is defined as the kth smallest element, where k is equal to len/2 + 1 if the length is odd, and k = len/2 if the length is even.
2. Code
Copy

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:


        heap = []
        merged = []
        lenght = len(nums1)+len(nums2)

        even = lenght % 2 == 0

        if len(nums1) == 0 or len(nums2) == 0:
            if len(nums1):
                heappush(heap,(nums1[0],nums1,0))
            if len(nums2):
                heappush(heap,(nums2[0],nums2,0))

        else:
            heappush(heap,(nums1[0],nums1,0))
            heappush(heap,(nums2[0],nums2,0))

      

        for i in range((lenght//2)+1):

            element,array,index=heappop(heap)
            merged.append(element)
            if index + 1 < len(array):
                heappush(heap,(array[index+1],array,index+1))

        if (even):
            return (merged[-1] + merged[-2])/2
        else: # odd
            return merged[-1]