LeetCode: Median of Two Sorted Arrays
题目
https://oj.leetcode.com/problems/median-of-two-sorted-arrays/
分析
如果这道题的时间复杂度要求是O(m+n)的话， 就很简单了， 直接merge之后找出中位数即可。
如果时间复杂度要求为O(log(m+n))的话， 可以把这道题转化为求第k小的问题。
-
如果(m+n)是奇数的话， 中位数就是第（m+n）/2+1小； 如果(m+n)是偶数， 中位数就是第(m+n)/2小和第(m+n)/2+1小的平均数。
-
然后问题是如何求解第k小的数？
假设有两个数组：
A[0], A[1], ......A[m-1]
B[0], B[1], ......B[n-1]
两数组合并后为
C[0], C[1], ...... C[m+n-1]
不妨假设m和n都大于k/2, 比较A[k/2-1]和B[k/2-1]，
如果A[k/2-1] < B[k/2-1]， 那么A[k/2-1]及其左侧的元素一定小于合并后的第k小的那个数（即C[k-1]）
为什么？
可以通过反证来证明，
假设A[k/2-1]等于合并后第k小元素 (即C[k-1]),
那么实际最多有多少个元素比A[k/2-1]小呢？ A[0], A[1]......A[k/2-2]以及B[0], B[1].......B[k/2-2]， 共k-2个元素。 也就是说A[k/2-1]最好情况下是第k-1小元素(即C[k-2])
这与假设矛盾， 因此假设不成立
因此可以说， A[k/2-1]及其左侧元素一定小于合并后的第k小那个数， 这样就可以排除掉这一范围的数，从而缩小了问题规模。
- 再来考虑递归基
当A为空或者B为空时， 返回B[k-1]或A[k-1]
当k == 1时， 返回A[0]和B[0]中较小的那个数
当A[k/2-1] == B[k/2-1]时， 返回A[k/2-1]
否则的话， 就递归缩小问题规模。
代码
class Solution
{
public:
double findMedianSortedArrays(int A[], int m, int B[], int n)
{
if ((m + n) & 0x01)
return findKth(A, m, B, n, (m + n) / 2 + 1);
else
return (findKth(A, m, B, n, (m + n) / 2)
+ findKth(A, m, B, n, (m + n) / 2 + 1)) / 2;
}
double findKth(int A[], int m, int B[], int n, int k)
{
if (m > n)
return findKth(B, n, A, m, k);
else if (m == 0)
return B[k-1];
else if (k == 1)
return min(A[0], B[0]);
else
{
int ALeftCount = min(k / 2, m);
int BLeftCount = k - ALeftCount;
if (A[ALeftCount-1] == B[BLeftCount-1])
return A[ALeftCount-1];
else if (A[ALeftCount-1] < B[BLeftCount-1])
return findKth(A+ALeftCount, m-ALeftCount,
B, n, k-ALeftCount);
else//A[ALeftCount-1] > B[BLeftCount-1]]
return findKth(A, m,
B+BLeftCount, n-BLeftCount, k-BLeftCount);
}
}
};
参考
http://blog.csdn.net/yutianzuijin/article/details/11499917
本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39156991