【LeetCode 4】Median of Two Sorted Arrays（Python)

Problem:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
           

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5
           

Solutions:

solution1:

     這個算法雖然在網站上通過了，但是算法複雜度并不是O(log(m+n))，而是O(m+n)，且算法實作複雜。

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        cache = []
        len_nums1 = len(nums1)
        len_nums2 = len(nums2)
        mid_idx = []
        total_len = len_nums1+len_nums2
        if total_len%2==0:
            mix_idx.extend([int(total_len/2)-1,int(total_len/2)])
        else:
            mid_idx.append(int(total_len/2))
        i1,i2=0,0
        for i in range(mid_idx[0]+1):
            if i1>=len_nums1:
                cache.append(nums2[i2+mid_idx[0]-i-1])
                if len(mix_idx)==2:
                    cache.append(nums2[i2+mid_idx[1]-i-1])
                break
            elif i2>=len_nums2:
                cache.append(nums1[i1+mid_idx[0]-i-1])
                if len(mix_idx)==2:
                    cache.append(nums1[i1+mid_idx[1]-i-1])
                break
            else:
                if nums1[i1]>=nums2[i2]:
                    i2+=1
                    if i==mid_idx[0]:
                        cache.append(nums2[i2-1])
                        if len(mid_idx)==2:
                            cache.append(min(nums1[i1],nums2[i2]))
                        break
                else:
                    i1+=1
                    if i==mid_idx[0]:
                        cache.append(nums1[i1-1])
                        if len(mid_idx)==2:
                            cache.append(min(nums1[i1],nums2[i2]))
                        break
        return sum(cache)/len(cache)
           

solution2:

       這個算法參考算法導論中講述的二分法的思想，算法複雜度為O(log(m+n))，較難想到，但非常巧妙

class Solution(object):
    def get_kth_num(self, nums1, nums2, k):
        len1 = len(nums1)
        len2 = len(nums2)
        if len1>len2:
            return self.get_kth_num(nums2,nums1,k)
        if len(nums1)==0:
            return nums2[k-1]
        elif k==1:
            return min(nums1[0],nums2[0])
        else:
            pa = min(len1, int(k/2))
            pb = k - pa
            if nums1[pa-1]>nums2[pb-1]:
                return self.get_kth_num(nums1,nums2[pb:],pa)
            else:
                return self.get_kth_num(nums1[pa:],nums2,pb)
            
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        len1 = len(nums1)
        len2 = len(nums2)
        k = int((len1+len2)/2)
        if k==0 or (len1+len2)!=2*k:
            return self.get_kth_num(nums1, nums2, k+1)
        else:
            return (self.get_kth_num(nums1, nums2, k) + self.get_kth_num(nums1, nums2, k+1))*0.5
           

solution 3:

      第三種解決方法為leetcode官方給出的解決方案，官方還提供了完整的分析思路，可自行查閱參考

def median(A, B):
    m, n = len(A), len(B)
    if m > n:
        A, B, m, n = B, A, n, m
    if n == 0:
        raise ValueError

    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if i < m and B[j-1] > A[i]:
            # i is too small, must increase it
            imin = i + 1
        elif i > 0 and A[i-1] > B[j]:
            # i is too big, must decrease it
            imax = i - 1
        else:
            # i is perfect

            if i == 0: max_of_left = B[j-1]
            elif j == 0: max_of_left = A[i-1]
            else: max_of_left = max(A[i-1], B[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = B[j]
            elif j == n: min_of_right = A[i]
            else: min_of_right = min(A[i], B[j])

            return (max_of_left + min_of_right) / 2.0