leetcode 004 Median of Two Sorted Arraysは2つの秩序配列の中位数python O(logn)を探している.

すべてのLeetcodeのテーマは不定期にGithubにまとめられ、批判と指摘を歓迎し、交流を討論します.

'''
# 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


'''




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

        m,n = len(nums1),len(nums2)
        if m > n:
            nums1, nums2, m, n = nums2, nums1, n ,m
        if m == 0:
            return (nums2[n//2] + nums2[(n-1)//2] )/2                #          ，     
        l , r = 0 , m
        k = (m + n + 1)//2
        while l < r:
            c1 = l + (r-l)//2
            c2 = k-c1
            if nums1[c1] < nums2[c2-1]:
                l = c1 +1
            else:
                r = c1
        c1 = l
        c2 = k - c1
        res1 = max(nums1[c1-1] if c1 > 0 else float("-inf"), nums2[c2-1] if c2 > 0 else float("-inf") )
        if (m + n) % 2 == 1:
            return res1
        res2 = min(nums1[c1] if c1 < m else float("inf"), nums2[c2] if c2 

すべてのLeetcodeのテーマは不定期にGithubにまとめられ、批判と指摘を歓迎し、交流を討論します.