转载

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)).

思路：

寻找中间的数，等价于寻找第 (m+n)/2 大的数，要求时间复杂度再 O(log (m+n)) ，其实就是告诉我们要用二分的方法在两个数组中找第 k 大的数，用以下方法递归查找（假设 a 数组长度比 b 小）：

若 a 数组长度为0，返回 b[k-1];
若 k == 1 ，返回 min(a[0], b[0]);
取 a 数组中值为 min(k/2, aSize) ，b 数组中值为 k - aMid

- 若 a[aMid] < b[bMid] ，递归在数组 a[aMid..aSize] 和 b[0..bSize] 中找第 k-aMid 大的元素
- 若 a[aMid] > b[bMid] ，递归在数组 a[0..aSize] 和 b[bMid..bSize] 中找第 k-bMid 大的元素
- 否则，第 a[aMid]就是所求的第 k 小的数。

简单解释一下递归思路：我们比较 a[k/2] 和 b[k/2] 两个元素，这两个元素分别表示 a 的第 k/2 小的元素和 b 的第 k/2 小的元素。如果 a[k/2] < b[k/2]，说明 a[0] 到 a[k/2] 的元素都在合并后的前k小的元素中，要找第 k 小的数，只需从 a[k/2] 到 a[aSize] 中找第 k/2 小的元素。

代码：

 1 #define min(a,b) (a) > (b)? (b) : (a)  2 double findKth(int * a, int aSize, int * b, int bSize, int k)  3 {  4     if (aSize > bSize)  5         return findKth(b, bSize, a, aSize, k);  6     if (aSize == 0)  7         return b[k - 1];  8     if (k == 1)  9         return min(a[0], b[0]); 10  11     int aMid = min(k / 2, aSize), bMid = k - aMid; 12     if (a[aMid - 1] < b[bMid - 1]) 13         return findKth(a + aMid, aSize - aMid, b, bSize, k - aMid); 14     else if (a[aMid - 1] > b[bMid - 1]) 15         return findKth(a, aSize, b + bMid, bSize - bMid, k - bMid); 16     else 17         return a[aMid - 1]; 18 } 19  20 double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) { 21     int total = nums1Size + nums2Size; 22     if (total % 2 == 1) 23         return findKth (nums1, nums1Size, nums2, nums2Size, total / 2 + 1); 24     else 25         return (findKth(nums1, nums1Size, nums2, nums2Size, total / 2) 26                 + findKth(nums1, nums1Size, nums2, nums2Size, total / 2 + 1)) / 2; 27 }