[LeetCode] Median of Two Sorted Arrays

Median of Two Sorted Arrays

There are two sorted arrays A and B 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(m+n)，不满足题目的要求。我完全没有思路，在网上查找的解题思路如下：

将原题看成是找第k小的数，递归查找结果。几个边界条件为：

实现代码：class Solution {public:double findMedianSortedArrays(int A[], int m, int B[], int n) {int total = m + n;if(total & 1 ) { //奇数return findKth(A, m, B, n, ((m + n) >> 1) + 1);}else{ //偶数return (findKth(A, m, B, n, (m + n) >> 1) + findKth(A, m, B, n, ((m + n) >> 1) + 1)) / 2;}}double findKth(int A[], int m, int B[], int n, int k){if(m > n){return findKth(B, n, A, m, k);}if(m == 0){return B[k – 1];}if(k == 1){return min(A[0], B[0]);}int pa = min(k >> 1, m), pb = k – pa;//排除小的那部分if(A[pa-1] < B[pb-1]){return findKth(A + pa, m – pa, B, n, k – pa);}else if(A[pa – 1] > B[pb – 1]){return findKth(A, m, B + pb, n – pb, k – pb);}else{return A[pa-1];}}private:int min(int a, int b){return a>b?b:a;}};有几个地方可以值得借鉴：状态转化思想，因为findKth不知道两个数组哪个更长些，为了免除不必要的判断，直接转化为其中一种状态，我们在编码的时候只需要考虑一种状态即可。

参考网址：

与那些新人和旧人们共同经历吧！