1717比较k/2位置处数字的大小,小的那一部分一定是在k小的数字之内(可以假设法证明),这样剩下的问题就是从剩下的列表中找
1818第k/2位数了.等到这个数为1,那么就好计算了.
1919
20+
21+ 注意:本解答仍然有问题。
22+
2023"""
2124
2225
@@ -38,6 +41,7 @@ def findMedianSortedArrays(self, nums1, nums2):
3841 len2 = len (nums2 )
3942
4043 if (len1 + len2 ) % 2 is 0 :
44+ return (self .__findKth (4 , nums1 , nums2 ))
4145 return (self .__findKth ((len1 + len2 ) / 2 + 1 , nums1 , nums2 ) + self .__findKth ((len1 + len2 ) / 2 , nums1 ,
4246 nums2 )) / 2.0
4347 else :
@@ -55,22 +59,21 @@ def __findMedian(li):
5559 def __findKth (k , l1 , l2 ):
5660 l1_start = 0
5761 l2_start = 0
58- k -= 1
59- while (len (l1 ) + len (l2 ) - l1_start - l2_start - 1 ) >= k :
60- if k is 0 :
62+ while (len (l1 ) + len (l2 ) - l1_start - l2_start ) >= k :
63+ if k is 1 :
6164 return min (l1 [l1_start ], l2 [l2_start ])
6265 if len (l1 ) - l1_start < len (l2 ) - l2_start :
63- l1_comp_start = l1_start + min (len (l1 ), k / 2 )
64- l2_comp_start = k - min (len (l1 ), k / 2 ) + l2_start
66+ l1_comp_start = l1_start + min (len (l1 ) - l1_start , k / 2 )
67+ l2_comp_start = k - min (len (l1 ) - l1_start , k / 2 ) + l2_start - 1
6568 else :
66- l2_comp_start = min (len (l2 ), k / 2 ) + l2_start
67- l1_comp_start = k - min (len (l2 ), k / 2 ) + l1_start
69+ l2_comp_start = min (len (l2 ) - l2_start , k / 2 ) + l2_start
70+ l1_comp_start = k - min (len (l2 ) - l2_start , k / 2 ) + l1_start - 1
6871
6972 if l1 [l1_comp_start ] > l2 [l2_comp_start ]:
70- k -= (l2_comp_start - l2_start )
73+ k -= (l2_comp_start - l2_start + 1 )
7174 l2_start = l2_comp_start + 1
7275 elif l1 [l1_comp_start ] < l2 [l2_comp_start ]:
73- k -= (l1_comp_start - l1_start )
76+ k -= (l1_comp_start - l1_start + 1 )
7477 l1_start = l1_comp_start + 1
7578 else :
7679 return l1 [l1_comp_start ]
@@ -79,7 +82,7 @@ def __findKth(k, l1, l2):
7982
8083def main ():
8184 print (Solution ().findMedianSortedArrays ([0 , 1 , 2 , 3 , 4 ], [0 , 1 , 2 ])) # 1
82- print (Solution ().findMedianSortedArrays ([], [1 ])) #
85+ # print(Solution().findMedianSortedArrays([], [1])) #
8386
8487
8588if __name__ == "__main__" :
0 commit comments