leetcode 004 Median of Two Sorted Arraysは2つの秩序配列の中位数python O(logn)を探している.
1561 ワード
すべてのLeetcodeのテーマは不定期にGithubにまとめられ、批判と指摘を歓迎し、交流を討論します.
すべての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にまとめられ、批判と指摘を歓迎し、交流を討論します.