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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理