题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/
题目:
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)).
解题思路:
这题乍一看挺简单,实则很难。根据题目所要求的时间复杂度能大概猜出要使用二分查找,但不能得出一个完整的思路。遂上网找了参考。
先用自己的话大概说下,再贴别人的解答。
在两个有序数组中找中间值,可以看作找两个有序数组中第 k (本题中 k 为 (m + n)/ 2)大小的数。
可以假定为,先找出两个数组各自第 k / 2 个元素,然后比较两者的大小。如果两者相等,则找到该数。如果两者不相等,较小者应处于第 k 小元素之前。然后再刨去较小者及其前面的元素,重复以上过程。
参考链接:http://blog.csdn.net/yutianzuijin/article/details/11499917
从medianof two sorted arrays中看到了一种非常好的方法。原文用英文进行解释,在此我们将其翻译成汉语。该方法的核心是将原问题转变成一个寻找第k小数的问题(假设两个原序列升序排列),这样中位数实际上是第 (m+n)/2 小的数。所以只要解决了第 k 小数的问题,原问题也得以解决。
首先假设数组 A 和 B 的元素个数都大于 k/2,我们比较 A[k/2-1] 和 B[k/2-1] 两个元素,这两个元素分别表示 A 的第 k/2 小的元素和 B 的第 k/2 小的元素。这两个元素比较共有三种情况:>、<和=。
如果A[k/2-1] < B[k/2-1],这表示 A[0] 到 A[k/2-1] 的元素都在 A 和 B合并之后的前 k 小的元素中。换句话说,A[k/2-1] 不可能大于两数组合并之后的第 k 小值,所以我们可以将其抛弃。
证明也很简单,可以采用反证法。假设 A[k/2-1] 大于合并之后的第k小值,我们不妨假定其为第(k+1)小值。由于 A[k/2-1] 小于 B[k/2-1],所以 B[k/2-1] 至少是第(k+2)小值。但实际上,在 A 中至多存在 k/2-1 个元素小于 A[k/2-1],B 中也至多存在 k/2-1个元素小于 A[k/2-1],所以小于 A[k/2-1] 的元素个数至多有 k/2+ k/2-2,小于 k,这与 A[k/2-1] 是第(k+1)的数矛盾。
当A[k/2-1]>B[k/2-1]时存在类似的结论。
当 A[k/2-1] = B[k/2-1] 时,我们已经找到了第 k 小的数,也即这个相等的元素,我们将其记为 m。由于在 A 和 B 中分别有 k/2-1 个元素小于 m,所以 m 即是第 k 小的数。(这里可能有人会有疑问,如果 k 为奇数,则 m 不是中位数。这里是进行了理想化考虑,在实际代码中略有不同,是先求 k/2,然后利用 k-k/2 获得另一个数。)
通过上面的分析,我们即可以采用递归的方式实现寻找第 k 小的数。此外我们还需要考虑几个边界条件:
如果 A 或者 B 为空,则直接返回 B[k-1] 或者 A[k-1];
如果 k 为1,我们只需要返回 A[0] 和 B[0] 中的较小值;
如果 A[k/2-1] = B[k/2-1],返回其中一个.
C实现:
double findKth(int a[], int m, int b[], int n, int k) {
//always assume that m is equal or smaller than n
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]);
//divide k into two parts
int pa = min(k / 2, 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];
}
int min(int a, int b) {
return a < b ? a : b;
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int total = nums1Size + nums2Size;
if (total & 0x1)
return findKth(nums1, nums1Size, nums2, nums2Size, total / 2 + 1);
else
return (findKth(nums1, nums1Size, nums2, nums2Size, total / 2)
+ findKth(nums1, nums1Size, nums2, nums2Size, total / 2 + 1)) / 2;
}
2078 / 2078 test cases passed.
Status: Accepted
Runtime: 20 ms
根据以上方法,自己用 java 实现了一下:
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
if(len % 2 == 0)
return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2;
else
return findKth(nums1, 0, nums2, 0, len / 2 + 1);
}
public static double findKth(int[] a, int start_a, int[] b, int start_b, int k) {
int m = a.length - start_a;
int n = b.length - start_b;
if(m > n)
return findKth(b, start_b, a, start_a, k);
if(m == 0)
return b[k - 1 + start_b];
if(k == 1)
return Math.min(a[start_a], b[start_b]);
int pa = Math.min(k / 2, m);
int pb = k - pa;
if(a[pa - 1 + start_a] < b[pb - 1 + start_b])
return findKth(a, start_a + pa, b, start_b, k - pa);
else if(a[pa - 1 + start_a] > b[pb - 1 + start_b])
return findKth(a, start_a, b, start_b + pb, k - pb);
else
return a[pa - 1 + start_a];
}
}
2078 / 2078 test cases passed.
Status: Accepted
Runtime: 608 ms