4 Median of Two Sorted Arrays

题目

4 Median of Two Sorted Arrays

题解

题目要求从两个已排序的数组中寻找中值，而寻找中值可以看成是寻找第K小数字的特例。为了找到第K小数字，我们需要在两个数组中把最小的K-1个数筛选出去，剩下的数字中最小的那一个就是我们要找的第K小数字。由于数组是已排序的，我们可以利用这个性质，设计一个分治算法，每次去掉一部分比目标数字小的数字。

（下文中的/符号均代表整数除法） 记第一个数组为A，第二个数组为B，取A[K/2]和B[K/2]作比较，若A[K/2]小于B[K/2]，由于数组A、B均已排序，则数组A的前K/2个数字都必然比第K小数字还要小，因此可以被去掉。同理，若A[K/2]大于B[K/2]则把数组B的前K/2个数字去掉。去掉K/2个数字后，K更新为K/2。

特殊情况：某个数组的长度N小于K/2。此时取这个数组的最后一个数字做比较，若这个数较小，则去掉该数组中的所有元素，K更新为K-N。

反复进行上述步骤，直到：

1. K=1 此时最小的K-1个数都已被筛选出去，只要把数组A、B中的第一个数字取出来，返回两个数字中的最小值即是我们要找的第K小数字
2. 某个数组已空 由于剩下的非空数组是已排序的，它的第K个元素就是我们要找的第K小数字

记数组A的长度为N，B的长度为M，N+M可能是奇数也可能是偶数。奇数时我们只要使K=(N+M+1)/2，进行一次查找就能算出中值；偶数时则要查找两次，一次K=(N+M+1)/2，另一次K=(N+M+2)/2，中值等于两次结果的平均值。注意到奇数时(N+M+1)/2=(N+M+2)/2，所以我们可以统一进行两次查找，返回两次结果的平均值

算法复杂度分析：由于每进行一次比较都能排除K/2个元素（或者使得某个数组为空，这样在下一次计算时就能直接返回结果），所以算法的复杂度是O(log (K)) = O(log (m+n))

代码

class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int size1 = nums1.size();
		int size2 = nums2.size();
		if (size1 > size2) {
			return findMedianSortedArrays(nums2, nums1);
		}

		int start1 = 0;
		int end1 = size1;
		int start2 = 0;
		int end2 = size2;

		double median1 = findKth(nums1, start1, end1,
			nums2, start2, end2,
			(size1 + size2 + 1) / 2);

		double median2 = findKth(nums1, start1, end1,
			nums2, start2, end2,
			(size1 + size2 + 2) / 2);

		return (median1 + median2) / 2.0;
	}

private:
	double findKth(vector<int>& nums1, int start1, int end1,
		vector<int>& nums2, int start2, int end2,
		int kth) {
		if (start1 >= end1) {
			return nums2[start2 + kth - 1];
		}

		if (start2 >= end2) {
			return nums1[start1 + kth - 1];
		}

		if (kth == 1) {
			return min(nums1[start1], nums2[start2]);
		}

		int index1 = 0;
		int index2 = 0;

		if (kth / 2 > end1 - start1) {
			index1 = end1 - 1;
		}
		else {
			index1 = start1 + (kth / 2) - 1;
		}
		int comp1 = nums1[index1];

		if (kth / 2 > end2 - start2) {
			index2 = end2 - 1;
		}
		else {
			index2 = start2 + (kth / 2) - 1;
		}
		int comp2 = nums2[index2];

		if (comp1 > comp2) {
			kth = kth - (index2 - start2) - 1;
			start2 = index2 + 1;
		}
		else {
			kth = kth - (index1 - start1) - 1;
			start1 = index1 + 1;
		}

		return findKth(nums1, start1, end1, nums2, start2, end2, kth);
	}
};