首页 > 编程语言 > 详细

python二分法及小tips

时间:2019-09-05 20:23:43      阅读:93      评论:0      收藏:0      [点我收藏+]

原题在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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!