给定两个大小为 m 和 n 的正序（从小到大）数组?nums1 和?nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为?O(log(m + n))。
你可以假设?nums1?和?nums2?不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
double findMedianSortedArrays( int *nums1, int nums1Size, int *nums2, int nums2Size ) {
double answer = 0.0;
int i1 = 0, i2 = 0, ti = 0, *tempArray = NULL;
tempArray = malloc( sizeof(*tempArray) * (nums1Size + nums2Size) );
while( i1 < nums1Size && i2 < nums2Size ) {
tempArray[ti++] = nums1[i1] <= nums2[i2] ? nums1[i1++] : nums2[i2++];
}
while( i1 < nums1Size ) {
tempArray[ti++] = nums1[i1++];
}
while( i2 < nums2Size ) {
tempArray[ti++] = nums2[i2++];
}
answer = (ti & 1) ? tempArray[ti / 2] * 2 : tempArray[ti / 2] + tempArray[ti / 2 - 1];
free( tempArray );
return answer / 2.0;
}
double findMedianSortedArrays( int *nums1, int nums1Size, int *nums2, int nums2Size ) {
int lasttime = 0, current = 0, len = nums1Size + nums2Size;
int half = len / 2;
for( int i1 = 0, i2 = 0, i = 0; i <= half; ++i ) {
lasttime = current; // 记录中位数上一次的位置的值.
if( i2 >= nums2Size || (i1 < nums1Size && nums1[i1] <= nums2[i2]) ) {
current = nums1[i1++];
} else if( i2 < nums2Size ) {
current = nums2[i2++];
}
}
return len & 1 ? current : (lasttime + current) / 2.0;
}
#define MIN( a, b ) ((a) <= (b) ? (a) : (b))
static int recursion( int a[], int aSize, int b[], int bSize, int k ) {
int kc2 = k / 2;
int ai = MIN( aSize, kc2 ) - 1, bi = MIN( bSize, kc2 ) - 1;
if( aSize < 1 || bSize < 1 ) {
return aSize < 1 ? b[k - 1] : a[k - 1];
}
if( k < 2 ) {
return MIN( a[0], b[0] );
}
if( a[ai] <= b[bi] ) {
return recursion( a + MIN( aSize, ai + 1 ), aSize - (ai + 1), b, bSize, k - (ai + 1) );
}
return recursion( a, aSize, b + MIN( bSize, bi + 1 ), bSize - (bi + 1), k - (bi + 1) );
}
double findMedianSortedArrays( int *nums1, int nums1Size, int *nums2, int nums2Size ) {
int len = nums1Size + nums2Size;
double answer = 0.0;
// 假设数组共有7个元素, 则:
// 中位数 = (第4个元素 + 第4个元素) / 2.0.
// 中位数 = (第(8/2)个元素 + 第(9/2)个元素) / 2.0.
// 假设数组共有8个元素, 则:
// 中位数 = (第4个元素 + 第5个元素) / 2.0.
// 中位数 = (第(9/2)个元素 + 第(10/2)个元素) / 2.0.
// 数组的元素数量不管是奇数还是偶数,
// 中位数都为 (第((len+1)/2)个元素 + 第((len+2)/2)个元素) / 2.0.
answer += recursion( nums1, nums1Size, nums2, nums2Size, (len + 1) / 2 );
answer += recursion( nums1, nums1Size, nums2, nums2Size, (len + 2) / 2 );
return answer / 2.0;
}
原文：https://www.cnblogs.com/hujunxiang98/p/12856219.html