###4. Median of Two Sorted Arrays
题目: https://leetcode.com/problems/median-of-two-sorted-arrays/
难度:
Hard
解法一：
这个题首先可以扩展为findKthSmallestSortedArray，不一定要是median，O(M+N)的算法跃然纸上，像mergesort一样，我们保持两个指针，p1和p2,然后一个一个来数，直到数到第k大的：
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
def findKthSmallestInSortedArrays(nums1, nums2, k):
p1, p2, p, v = 0, 0, 0, 0
while p1 < len(nums1) and p2 < len(nums2) and p != k:
if nums1[p1] < nums2[p2]:
v = nums1[p1]
p1 += 1
else:
v = nums2[p2]
p2 += 1
p += 1
if p == k:
return v
elif p1 == len(nums1):
return nums2[k - p1 - 1]
else :
return nums1[k - p2 - 1]
if (len(nums1) + len(nums2)) % 2 == 0 :
return (findKthSmallestInSortedArrays(nums1,nums2,(len(nums1)+len(nums2))/2+1) + findKthSmallestInSortedArrays(nums1,nums2,(len(nums1)+len(nums2))/2))/2.0
else:
return findKthSmallestInSortedArrays(nums1,nums2,(len(nums1)+len(nums2))/2+1)注意各种边界条件，网上也很容易找到写的更简洁和精美的书写。
想到了类似的题目： merge two sorted list, merge k sorted lists(用heap).
解法二:
这个题跟CLRS书上的一道习题类似 求X[1....n] Y[1....n] 的 median
习题 9.3-8
Let X[1..n] and Y [1..n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithn to find the median of all 2n elements in arrays X and Y .
The median can be obtained recursively as follows. Pick the median of the sorted array A. This is just O(1) time as median is the n/2th element in the sorted array. Now compare the median of A, call is a∗ with median of B, b∗. We have two cases.
-
a∗ < b∗ : In this case, the elements in B[n/2 ···n] are also greater than a . So the median cannot lie in either A[1 · · · n/2 ] or B[n/2 · · · n]. So we can just throw these away and recursively
-
a∗ > b∗ : In this case, we can still throw away B[1··· n/2] and also A[ n/ · · · n] and solve a smaller subproblem recursively.
In either case, our subproblem size reduces by a factor of half and we spend only constant time to compare the medians of A and B. So the recurrence relation would be T (n) = T (n/2) + O(1) which has a solution T (n) = O(log n).
divide and conquer
- 如果X[n/2] == Y[n/2]，则找到，return
- 如果X[n/2] < Y[n/2],找X[n/2+1….n]和Y[1,2…n/2]之间
- 否则找X[1..n/2]和Y[n/2…n]
这里需要考虑的问题更多：
- 两个数组长度不一样 (可能甚至一个array都不至于到一半的数组)
- 并不是只找一个median，如果median有两个，需要算平均
思路
把它转化成findKth问题
参考： http://chaoren.is-programmer.com/posts/42890.html
首先转成求A和B数组中第k小的数的问题, 然后用k/2在A和B中分别找。
比如k = 6, 分别看A和B中的第3个数, 已知 A1 < A2 < A3 < A4 < A5... 和 B1 < B2 < B3 < B4 < B5..., 如果A3 <＝ B3, 那么第6小的数肯定不会是A1, A2, A3, 因为最多有两个数小于A1, 三个数小于A2, 四个数小于A3。所以可以抛掉 A1, A2, A3。
B3至少大于5个数, 所以第6小的数有可能是B1 (A1 < A2 < A3 < A4 < A5 < B1), 有可能是B2 (A1 < A2 < A3 < B1 < A4 < B2), 有可能是B3 (A1 < A2 < A3 < B1 < B2 < B3)。那就可以排除掉A1, A2, A3, 转成求A4, A5, ... B1, B2, B3, ...这些数中第3小的数的问题, k就被减半了，因为最小的3个数（×），因为一定在第5小之中的3个数被抛弃，所以我们需要求剩下的当中第三小的，这样它就是总的里面第6小的。
这里还有的问题是我们假设了k是偶数，如果k是奇数，比如第5小的，其实问题也不大，如果我们的函数样子是 findNthSmallestSortedArrays(A, B, n)，那么传入的是会是 k 和 k - k/2。
需要考虑一些终止条件和特定状况，比如某个array长度不足 k/2，比如是A更短，那么很简单，我们可以直接剔除掉B1 < B2 < B3 < B[k/2]，因为无论A[-1]如何小，或者说A[-1]都小于B1了，但是 len(A) + k/2 一定小于k，所以我们只需要去A 和 B[k/2:]中去寻找。(感觉这里也可以采用别的分割方式，但是明显这样是最简单的）。
之所以这里还有一个丢弃条件是b is None 丢A的一部分，是因为B的数组长度是有限的，这个时候很明显丢A的k/2是不影响的，因为无论B[-1]是如何大或者小，因为整个B的长度没有达到k/2，所以丢掉的这部分最大的A[k/2-1]也不可能是第k个，因为即使整个B都比A[k/2-1]，拼起来也不能使A[k/2-1]第k大，所以可以放心丢弃。
以下也是我见过的最优雅的解这个的代码：
这个跟习题算法的区别是每次扔的东西明显少一些，但是k也在不断变小。.
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
n = len(nums1) + len(nums2)
if n % 2 == 1:
return self.findKth(nums1, nums2, n / 2 + 1)
else:
smaller = self.findKth(nums1, nums2, n / 2)
bigger = self.findKth(nums1, nums2, n / 2 + 1)
return (smaller + bigger) / 2.0
def findKth(self, A, B, k):
if len(A) == 0:
return B[k-1]
if len(B) == 0:
return A[k-1]
if k == 1 :
return min(A[0],B[0])
# kth smallest, that is k - 1, so also k/2 - 1
a = A[ k / 2 - 1 ] if len(A) >= k / 2 else None
b = B[ k / 2 - 1 ] if len(B) >= k / 2 else None
if b is None or (a is not None and a < b):
return self.findKth(A[k/2:], B, k - k/2)
return self.findKth(A, B[k/2:],k - k/2)