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