之前写过一篇，这是第二篇。上一篇用了多种编程语言来做，这一次是以学算法为主，所以打算都用python来完成。
4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
这道题比较难，参考了这篇文章http://blog.csdn.net/yutianzuijin/article/details/11499917/，然后用python写了程序
其中第k小数算法是关键。总结下思路，争取以后我也可以多发明些这类nb的算法。
主要是将求A得问题巧妙地转换为求B的问题，并且在逻辑上证明是合理的。
class Solution(object):
def findKth(self, arr1, len1, arr2, len2, k):
#always assume that len1 is equal or smaller than len2
if len1 > len2:
return self.findKth(arr2, len2, arr1, len1, k)
if len1 == 0:
return arr2[k - 1]
if k == 1:
return min(arr1[0], arr2[0])
#divide k into two parts
pa = min(k / 2, len1)
pb = k - pa
if arr1[pa - 1] < arr2[pb - 1]:
return self.findKth(arr1[pa:], len1 - pa, arr2, len2, k - pa)
elif arr1[pa - 1] > arr2[pb - 1]:
return self.findKth(arr1, len1, arr2[pb:], len2 - pb, k - pb)
else:
return arr1[pa - 1]
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
nums1_len = len(nums1)
nums2_len = len(nums2)
total = nums1_len + nums2_len
if total & 1:
return self.findKth(nums1, nums1_len, nums2, nums2_len, total/2 + 1)
else:
ret1 = self.findKth(nums1, nums1_len, nums2, nums2_len, total/2)
ret2 = self.findKth(nums1, nums1_len, nums2,nums2_len, total/2 + 1)
return float((ret1 + ret2)) / 2