給兩個已經(jīng)排序的list，求中位數(shù)
直接二分結(jié)果，然后在兩個list分別二分確定位置，到達(dá)中間位置之后再精確求中位數(shù)并輸出，輸出那里調(diào)了幾次，WA了幾次，然后代碼就整得又臭又長 ==||
AC之后看Discussion，原來直接sort完求中位數(shù)就能過啊，我這樣二分反而慢，不科學(xué)啊，這可是標(biāo)為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