原题在https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums1.extend(nums2)
nums1.sort()
len1 = len(nums1)
return (nums1[len1//2 -1]+nums1[len1//2 ])/ 2.0 if len1 % 2 == 0 else nums1[int(len1/2)]
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
n1 = len(nums1)
n2 = len(nums2)
if n1 > n2 :
return self.findMedianSortedArrays(nums2,nums1)
k = (n1 + n2 +1 )//2
left = 0
right = n1
while left < right :
m1 = left + (right - left)//2
m2 = k - m1
if nums1[m1] <nums2[m2-1] :
left = m1 + 1
else:
right = m1
m1 = left
m2 = k -m1
c1 = max(nums1[m1 - 1] if m1 > 0 else float("-inf"), nums2[m2 - 1] if m2 > 0 else float("-inf"))
if (n1 + n2) % 2 == 1:
return c1
c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 < n2 else float("inf"))
return (c1+c2)/2
tips:
nums1.extend(nums2)
,nums1合取nums2 的数成为一个数组nums1.sort()
排序(默认升序,降序为nums1.sort(reverse = True)
)这个Leetcode的题目算法很有意思!!!
原文:https://www.cnblogs.com/thenbz3/p/11469146.html