这是崔斯特的第十一篇原创文章
1、题目
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
2、思路
蛋疼的说，我有看不懂题目了，尤其是O(log (m+n))，啥玩意。没办法，去网上搜索，看看前辈们的想法。
翻译如下：
给你两个排序数组，容量为m的数组A，容量为n的数组B。求出两个数组的中位数（啥玩意？），硬性要求时间复杂度O(log (m+n)).
1：太汗颜了，median到底是个啥，查一下：
中位数是在一组数据中居于中间的数(特别注意的地方是：这组数据之前已经经过升序排列！！！)，即在这组数据中，有一半的数据比它大，有一半的数据比它小。如果这组数据包含偶数个数字，中值是位于中间的两个数的平均值。
2：好吧，中位数是这么个玩意，那么理论上首先我们需要先将两个数组合为一，再求这个新合并的数组的中位数。
3：但是，已经限定死了时间复杂度为log（m+n），原来LeetCode的题目也思路不开放嘛。
4：问题可以转化成两个有序序列找第num大的数，由于时间复杂度已经限定死了，只能采用类似二分的思想，每个步骤去掉一半数据元素。
出现了一个词语：时间复杂度，这是个啥？
完全不懂，换个思路来吧，不去看题目了，直接看第四点：
问题可以转化成两个有序序列找第num大的数，由于时间复杂度已经限定死了，只能采用类似二分的思想，每个步骤去掉一半数据元素。
二分，又是二分，赶紧去复习下。
二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。
这个好像还可以看得懂，嘿嘿。我还发现了Python源代码（百度这样说的）：
def bin_search(data_list, val):
low = 0 # 最小数下标
high = len(data_list) - 1 # 最大数下标
while low <= high:
mid = (low + high) // 2 # 中间数下标
if data_list[mid] == val: # 如果中间数下标等于val, 返回
return mid
elif data_list[mid] > val: # 如果val在中间数左边, 移动high下标
high = mid - 1
else: # 如果val在中间数右边, 移动low下标
low = mid + 1
return # val不存在, 返回None
ret = bin_search(list(range(1, 10)), 3)
print(ret)
大概明白他的意思了。
3、解法
很多解法都提到：如果我们可以在两个数列中求出第K小的元素，便可以解决该问题
解题思路：这道题要求两个已经排好序的数列的中位数。中位数的定义：如果数列有偶数个数，那么中位数为中间两个数的平均值；如果数列有奇数个数，那么中位数为中间的那个数。比如{1，2，3，4，5}的中位数为3。{1，2，3，4，5，6}的中位数为（3+4）/ 2 = 3.5。那么这题最直接的思路就是将两个数列合并在一起，然后排序，然后找到中位数就行了。可是这样最快也要O((m+n)log(m+n))的时间复杂度，而题目要求O(log(m+n))的时间复杂度。这道题其实考察的是二分查找，是《算法导论》的一道课后习题，难度还是比较大的。
首先我们来看如何找到两个数列的第k小个数，即程序中getKth(A, B , k)函数的实现。用一个例子来说明这个问题：A = {1，3，5，7}；B = {2，4，6，8，9，10}；如果要求第7个小的数，A数列的元素个数为4，B数列的元素个数为6；k/2 = 7/2 = 3，而A中的第3个数A[2]=5；B中的第3个数B[2]=6；而A[2]<B[2]；则A[0]，A[1]，A[2]中必然不可能有第7个小的数。因为A[2]<B[2]，所以比A[2]小的数最多可能为A[0], A[1], B[0], B[1]这四个数，也就是说A[2]最多可能是第5个大的数，由于我们要求的是getKth(A, B, 7)；现在就变成了求getKth(A’, B, 4)；即A’ = {7}；B不变，求这两个数列的第4个小的数，因为A[0]，A[1]，A[2]中没有解，所以我们直接删掉它们就可以了。这个可以使用递归来实现。
class Solution:
# @return a float
# @line20 must multiply 0.5 for return a float else it will return an int
def getKth(self, A, B, k):
lenA = len(A); lenB = len(B)
if lenA > lenB: return self.getKth(B, A, k)
if lenA == 0: return B[k - 1]
if k == 1: return min(A[0], B[0])
pa = min(k/2, lenA); pb = k - pa
if A[pa - 1] <= B[pb - 1]:
return self.getKth(A[pa:], B, pb)
else:
return self.getKth(A, B[pb:], pa)
def findMedianSortedArrays(self, A, B):
lenA = len(A); lenB = len(B)
if (lenA + lenB) % 2 == 1:
return self.getKth(A, B, (lenA + lenB)/2 + 1)
else:
return (self.getKth(A, B, (lenA + lenB)/2) + self.getKth(A, B, (lenA + lenB)/2 + 1)) * 0.5
在我提交了代码之后，发现超过50.24 %
我找出最快的解法，来学习下：
class Solution(object):
def findMedianSortedArrays(self, a, b):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
c = a+b
c.sort()
m = len(c) / 2
mm = len(c) % 2
if mm > 0 :
return c[m]
return (c[m-1]+c[m])/2.# + (c[m-1]+c[m])%2
第二名的：
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
nums3 = nums1 + nums2
nums3.sort()
l = len(nums3)
if l%2 == 1:
return nums3[l/2]
else:
return (float(nums3[l/2]) + float(nums3[l/2-1]))/2
每做一题，都会被打击好多次，但是算法是一定要学习的。