• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594
            給兩個已經排序的list,求中位數

            直接二分結果,然后在兩個list分別二分確定位置,到達中間位置之后再精確求中位數并輸出,輸出那里調了幾次,WA了幾次,然后代碼就整得又臭又長  ==||
            AC之后看Discussion,原來直接sort完求中位數就能過啊,我這樣二分反而慢,不科學啊,這可是標為Hard的題啊

            直接sort

             1 #4
             2 #Runtime: 54 ms (Beats 92.77%)
             3 #Memory: 13.3 MB (Beats 88.11%)
             4 
             5 class Solution(object):        
             6     def findMedianSortedArrays(self, nums1, nums2):
             7         """
             8         :type nums1: List[int]
             9         :type nums2: List[int]
            10         :rtype: float
            11         """
            12         nums = nums1 + nums2
            13         nums.sort()
            14         n = len(nums)
            15         if n % 2 == 0:
            16             return 0.5 * (nums[(n // 2) - 1] + nums[(n // 2)])
            17         return nums[(n - 1) // 2]

            二分

             1 #4
             2 #Runtime: 244 ms
             3 #Memory Usage: 13.5 MB
             4 
             5 class Solution(object):        
             6     def findMedianSortedArrays(self, nums1, nums2):
             7         """
             8         :type nums1: List[int]
             9         :type nums2: List[int]
            10         :rtype: float
            11         """ 
            12         if len(nums1) == 0:
            13             if len(nums2) % 2 == 0:
            14                 return (float(nums2[int(len(nums2)/2) - 1]) + float(nums2[int(len(nums2)/2)])) / 2
            15             else:
            16                 return float(nums2[int(len(nums2)/2)])
            17         if len(nums2) == 0:
            18             if len(nums1) % 2 == 0:
            19                 return (float(nums1[int(len(nums1)/2) - 1]) + float(nums1[int(len(nums1)/2)])) / 2
            20             else:
            21                 return float(nums1[int(len(nums1)/2)])
            22         l = float(min(nums1[0], nums2[0]))
            23         r = float(max(nums1[-1], nums2[-1]))
            24         l1 = 0
            25         r1 = len(nums1)
            26         l2 = 0
            27         r2 = len(nums2)
            28         if l == r:
            29             return float(l)
            30         while r - l > 0.000001:
            31             mid = (l + r) / 2
            32             mid1 = 0
            33             mid2 = 0
            34             ll1 = l1
            35             rr1 = r1
            36             while ll1 < rr1:
            37                 mid1 = int((ll1 + rr1) / 2)
            38                 if nums1[mid1 - 1] < mid:
            39                     ll1 = mid1 + 1
            40                 else:
            41                     rr1 = mid1
            42             mid1 = int((ll1 + rr1) / 2)
            43             f1 = 0
            44             if nums1[mid1 - 1] > mid:
            45                 mid1 = max(0, mid1 - 0.5)
            46             elif nums1[mid1 - 1] == mid:
            47                 f1 = 1
            48             else:
            49                 mid1 = min(r1, mid1 + 0.5)
            50             ll2 = l2
            51             rr2 = r2
            52             while ll2 < rr2:
            53                 mid2 = int((ll2 + rr2) / 2)
            54                 if nums2[mid2 - 1] < mid:
            55                     ll2 = mid2 + 1
            56                 else:
            57                     rr2 = mid2
            58             mid2 = int((ll2 + rr2) / 2)
            59             f2 = 0
            60             if nums2[mid2 - 1] > mid:
            61                 mid2 = max(0, mid2 - 0.5)
            62             elif nums2[mid2 - 1] == mid:
            63                 f2 = 1
            64             else:
            65                 mid2 = min(r2, mid2 + 0.5)
            66             if f1 == 1 and f2 == 1:
            67                 return (nums1[mid1 - 1] + nums2[mid2 - 1]) / 2.0
            68             if f1 == 0 and f2 == 0 and 2 * (int(mid1) + int(mid2)) == r1 + r2:
            69                 a = []
            70                 b = []
            71                 if int(mid1) - 1 >= 0:
            72                     a.append(nums1[int(mid1) - 1])
            73                 if int(mid2) - 1 >= 0:
            74                     if len(a) > 0:
            75                         a[0] = max(a[0], nums2[int(mid2) - 1])
            76                     else:
            77                         a.append(nums2[int(mid2) - 1])
            78                 if int(mid1) < len(nums1):
            79                     b.append(nums1[int(mid1)])
            80                 if int(mid2) < len(nums2):
            81                     if len(b) > 0:
            82                         b[0] = min(b[0], nums2[int(mid2)])
            83                     else:
            84                         b.append(nums2[int(mid2)])
            85                 return (a[0] + b[0]) / 2.0
            86             if f1 == 0 and f2 == 1 and 2 * (int(mid1) + int(mid2)) == r1 + r2:
            87                 return nums2[int(mid2) - 1]
            88             if f1 == 1 and f2 == 0 and 2 * (int(mid1) + int(mid2)) == r1 + r2:
            89                 return nums1[int(mid1) - 1]
            90             if 2 * (int(mid1) + int(mid2)) < r1 + r2:
            91                 l = mid + 0.0000001
            92             else:
            93                 r = mid - 0.0000001
            94         return mid
            浪潮AV色综合久久天堂| 久久久久国色AV免费看图片| 久久久久久久久久久| 久久免费看黄a级毛片| 91精品国产色综合久久| 久久精品这里只有精99品| 精品一二三区久久aaa片| 精品999久久久久久中文字幕| 国产精品99久久久久久www| 久久精品综合网| 国产精品久久久99| 热re99久久6国产精品免费| 精品无码久久久久久国产| 久久久久久午夜成人影院| 久久久久亚洲AV综合波多野结衣 | 国内精品久久久久影院日本| 一本伊大人香蕉久久网手机| 久久精品中文字幕一区| 91久久精品视频| 久久99国产精品二区不卡| 精品久久亚洲中文无码| 中文成人久久久久影院免费观看| 国产美女久久久| 久久精品国产亚洲AV无码娇色 | 久久久99精品成人片中文字幕| 人妻无码中文久久久久专区| 噜噜噜色噜噜噜久久| 久久久久久国产精品无码下载 | 久久久国产视频| 久久久久久免费视频| 久久久久亚洲精品无码网址| 狠狠人妻久久久久久综合| 久久久青草久久久青草| 久久青青草原精品影院| 亚洲乱亚洲乱淫久久| 久久综合久久综合久久| 久久美女网站免费| 久久精品成人免费国产片小草 | 欧美va久久久噜噜噜久久| 久久亚洲精品人成综合网 | 国产精品亚洲综合专区片高清久久久 |