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)).
Subscribe to see which companies asked this question
分析：
这个题目在leetcode 中难度级别为hard。其实如果没有限定复杂度为O(log(m+n))，那么难度就要下降不少。
首先对于中位数这个概念，如果两个数组size 之和为奇数，那么中位数就是中间的那个数；否则中位数是中间两个数相加后的平均值。
关于两个有序数组的findKth，可以先比较两个数组A[m], B[n]的k/2位置，假设值为A[k/2 - 1] 和 B[k/2 - 1]:
最终演化为一个递归的策略，每次递归都可以去除一部分内容，并同时缩小K 的值，最终可以找到答案。
递归方案：
note: findKth 的K是从1开始，而且要注意K与数组索引之间的关系，小心找到前一个或后一个位置。
实现代码：
Merge Sort 方案：
double merge(int *nums1, int nums1Size, int *nums2, int nums2Size)
{
double result = 0.0;
int totalSize = nums1Size + nums2Size;
int mid = totalSize >> 1;
int nums1Index = 0;
int nums2Index = 0;
int *nums = (int *)malloc((mid+1) * sizeof(int));
for (int index = 0; index <= mid; index++) {
if (nums1Index >= nums1Size) {
nums[index] = nums2[nums2Index++];
}
else if (nums2Index >= nums2Size) {
nums[index] = nums1[nums1Index++];
}
else if (nums1[nums1Index] < nums2[nums2Index]) {
nums[index] = nums1[nums1Index++];
}
else {
nums[index] = nums2[nums2Index++];
}
}
if ((nums1Size + nums2Size) & 0x01) {
result = nums[mid];
}
else {
result = (nums[mid-1] + nums[mid])/2.0;
}
free(nums);
return result;
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
return merge(nums1, nums1Size, nums2, nums2Size);
}
FindKth 方案：
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/2, m);
int 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];
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int mid = (nums1Size + nums2Size) >> 1;
if ((nums1Size + nums2Size) & 0x01) {
return findKth(nums1, nums1Size, nums2, nums2Size, mid+1);
}
else {
return (findKth(nums1, nums1Size, nums2, nums2Size, mid)
+ findKth(nums1, nums1Size, nums2, nums2Size, mid + 1)) / 2.0;
}
}
在Leetcode 中实际提交时，这两个方案都能达到最优的20ms 结果。
[LeetCode] Median of Two Sorted Arrays 解题报告
原文：http://www.cnblogs.com/jiaochen/p/5581424.html