4. Median of Two Sorted Arrays
这题基本想法是扔一半，比如说取第k大的数，那么则比较nums1[k/2-1] 和nums2[k/2-1] 例如 nums1[k/2]这个值比较大，则说明第k大的数肯定不再nums2的 0 ～ k/2-1的这个范围内，全部扔掉。这时候再递归的时候nums2 从 0 + k/2开始计数，而k的值也相应的缩小为 k - k／2。最tricky的地方，也是我花了一些时间的地方，就是到底从哪里开始计数，扔掉多少，新的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)
