leetcode-4. 寻找两个正序数组的中位数

leetcode-4. 寻找两个正序数组的中位数。

给定两个大小为 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/problemset/all/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：辅助数组对原来的两数组进行归并。

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;
}

解法三：求中位数其实就是求第 k 小数的一种特殊情况。

前面解法的遍历过程中每次只去掉一个不可能是中位数的元素,
由于数列是有序的,其实完全可以一半一半的排除,
假设要找第 k 小的元素, 遍历过程中每次排除掉 k/2 个元素.
参考： https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

#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;
}