4. Median of Two Sorted Arrays
這題基本想法是扔一半，比如說取第k大的數(shù)秸讹，那么則比較nums1[k/2-1] 和nums2[k/2-1] 例如 nums1[k/2]這個值比較大，則說明第k大的數(shù)肯定不再nums2的 0 ～ k/2-1的這個范圍內(nèi)稠通，全部扔掉钮科。這時候再遞歸的時候nums2 從 0 + k/2開始計數(shù)，而k的值也相應(yīng)的縮小為 k - k／2彼乌。最tricky的地方泻肯，也是我花了一些時間的地方，就是到底從哪里開始計數(shù)囤攀，扔掉多少软免，新的pointer更新為多少，k一定要從1開始count焚挠，否則不太好做膏萧。
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
# 和kth largest number in two sorted array 類似
l = len(nums1) + len(nums2)
if l % 2 != 0:
return self.kth(nums1, nums2, 0, 0, l/2+1)
else:
return (self.kth(nums1, nums2, 0, 0, l/2) + self.kth(nums1, nums2, 0, 0, l/2+1)) / 2.0
def kth(self, nums1, nums2, p1, p2, k):
""" find kth element """
# k is kth element counting from 1
if p1 >= len(nums1):
return nums2[p2+k-1]
if p2 >= len(nums2):
return nums1[p1+k-1]
if k == 1:
return min(nums1[p1], nums2[p2])
if p1+k/2-1 >= len(nums1):
cur1 = sys.maxint
else:
cur1 = nums1[p1+k/2-1]
if p2+k/2-1 >= len(nums2):
cur2 = sys.maxint
else:
cur2 = nums2[p2+k/2-1]
if cur1 > cur2:
return self.kth(nums1, nums2, p1, p2+k/2, k - k/2)
else:
return self.kth(nums1, nums2, p1+k/2, p2, k - k/2)
