python二分法及小tips

原题在https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

1. 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)]

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)）
• float("-inf")，float("inf") 表示正负无穷

这个Leetcode的题目算法很有意思！！！

python二分法及小tips

原文：https://www.cnblogs.com/thenbz3/p/11469146.html