一、题目
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)).
二、解析
该题是让求两个有序序列的中位数，时间复杂度为O(log(m+n))。其实拿到这个题第一想法是把两个序列合并成一个，然后直接输出中间的元素即可，这样的话两个list每个元素都要过一遍，所以复杂度为O（m+n）。由于LeetCode本题数据太弱，所以随便一试就过了，额。。见代码一。
但是注意到时间复杂度，和“有序”这个条件，则说明可以用折半的方法去做。一时没了想法，如何用折半？去看Discuss，基本都是将求中位数的问题转化成求第K小的问题。什么意思呢？比如a=[1,2,3,4,5]，中位数就是第三个元素3，也就是第3小的数。找到这个数即可。既然复杂度要求这么高，那么一定是不能进行合并、从头遍历这样的操作的，所以问题转化成为：在不合并两个序列的情况下，找出合并后应有的中位数。参照他人思路，有以下共识：
首先假设a=[7,8,9], b = [1,2,3,5]，中位数为5，转化为找第（3+4）/2 + 1 = 4小的数。既然找第k小，那么找到一个小的，就算是完成了任务的一部分。
1、首先找a的中位数8.b的中位数2，发现8>2，说明合并后的中位数，在靠左一些的位置。这样以来，我们就找到了两个比较小的数，为b中2的左边（1，2），一共2个。这时问题就转化成：在a[7,8,9]和b[3,5]中找到第2小的数。
2、重复上面的过程，a中位数为8，b中位数为3，8>3，则说明合并后的中位数在8左边位置。b中3的左边（3），一共一个，问题转化成a[7,8,9]中和b[5]中找到第1小的数
3、还这么找，8>5，记录下5，发现5就是目前a[7,8,9],b[5]中第一小的数，则完成，并返回。
这里的折半体现在哪里呢？在上述描述中，折半直观上体现在b上：就统计小的个数后，就删去前半部分，只留后半部分，并且将寻找第k小变成寻找k-i小。这个在a中能不能体现呢？是不是8>3，那么8的右边就也可以删了呢？
这是不行的，假设问题是要找第8小，那么第一步进来8>2，统计2小，删去后b变成[3,5]；一个很容易出错的思想就是，删除a的左边，删除b的右边，b变成[7,8]，折半+折半多好。其实这个是不对的，因为我们发现，只有小的数才能影响我们的技术结果，找到i个，就只用再找k-i个就可以了。而至于那些大的，如果本身要找的k比较多，比如说k=8，要找第8小的，其实就是a中的9，如果b成了[7,8]，就傻咯，找不到了。
所以折半和找第k小是分离的，折半找出一些小的数，让找第k小更容易一些。否则遍历的话，发现一个小的，计数器+1，这样是O(n)。
三、Python代码
1、O（m+n）方法：合并成一个序列求中位数
1 class Solution: 2 # @param {integer[]} nums1 3 # @param {integer[]} nums2 4 # @return {float} 5 def findMedianSortedArrays(self, nums1, nums2): 6 merge = nums1 + nums2 7 merge.sort() 8 m = len(nums1) 9 n = len(nums2) 10 total = m + n 11 if total % 2 == 1: 12 return merge[total/2] 13 else: 14 return float(merge[total/2] + merge[total/2 - 1]) / 2
2、O（log(m+n)）
1 class Solution: 2 # @param {integer[]} nums1 3 # @param {integer[]} nums2 4 # @return {float} 5 def findkth(self, s, l, k): 6 # s stands for short-list, l stands for long-list, and k stands for the kth smallest in the list. 7 m = len(s) 8 n = len(l) 9 10 # ensure the 1st list is short and the 2nd list is long 11 if m > n: 12 return self.findkth(l, s, k) 13 14 #s is empty, so the kth small in l[k-1] 15 if not s: 16 return l[k - 1] 17 18 #the last one small number, compare s[0] and l[0] cause the list is orderd. 19 if k == 1: 20 return min(s[0], l[0]) 21 22 #get the mid of the current list s and l 23 i = min(m, k / 2) 24 j = min(n, k / 2) 25 26 #the s[mid] > l[mid], cut the small in l by using l[j:], and get update the kth: k - j 27 if s[i - 1] > l[j - 1]: 28 return self.findkth(s, l[j:], k - j) 29 else: 30 return self.findkth(s[i:], l, k - i) 31 32 33 def findMedianSortedArrays(self, nums1, nums2): 34 len_1 = len(nums1) 35 len_2 = len(nums2) 36 l = len_1 + len_2 37 rst = 0.0 38 39 #even and odd 40 if l % 2 == 1: 41 rst = self.findkth(nums1, nums2, (l + 1) / 2) / 1.0 42 else: 43 rst = (self.findkth(nums1, nums2, (l + 1) / 2) + self.findkth(nums1, nums2, (l + 2) / 2)) / 2.0 44 45 return rst
四、总结
1、要坚持把自己脑海中的东西说出来，这样一些自己一直有疑惑的问题写着写着就想明白了。
之前我自己一直处于混沌状态，直到把这篇解题报告写完，才清楚了许多。之前一直什么搞不清楚呢，就是折半怎么用的问题。虽然大家都说a>b，则b的左边一半就不用看了，我也知道，但就是不知道为什么。写完这篇才知道，不用看的意思是，不用再去一个一个数左边到底有几个小的了。其实上面解析部分，讨论要不要去掉a中右边的一半，就是我一直疑惑的地方。
2、一定要抓住痛点，知道好的算法是要解决什么问题的。
也是刚刚才想清楚本题用折半是用来做什么的。要找第k大，如何找？容易想到的有以下方法：
1）从小到达排序，然后找第a[mid]，排序复杂度为O(N)，查找为O(1)
2) 不排序，直接遍历找，设置一个最大值和计数器。发现一个比最大值大的，就更新最大值，计数器+1，复杂度O（n）
要解决的问题是什么？要找第k大的值。疼点在什么？慢。那折半怎么就快了？一下能确定好多个。这不就结了！而不在于说形式上的，左边不要，只要右边。要知道不要以后，那些不要的数据去哪儿了。
3、写解题思路是很有用的，比如今天又用到了子函数，忘了调用，写成this.findkth，提交一直报错，看了之前的解题笔记，才发现是self.findkth，哈~~
#4 Median of Two Sorted Arrays
原文：http://www.cnblogs.com/breada/p/4645862.html