LeetCode Median of Two Sorted Arrays两数列的中间数

Median of Two Sorted Arrays

There are two sorted arrays A and B 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)).

感觉本题并不难，如果用简单的方法做的话，好像很容易就通过了。

比如合并成一个数组，然后排序，然后直接返回中间数，也可以通过的，如下程序：

double findMedianSortedArrays(int A[], int m, int B[], int n) {
		vector<int> vab(A, A+m);
		for (int i = 0; i < n; i++)
		{
			vab.push_back(B[i]);
		}
		sort(vab.begin(), vab.end());
		int k = (m+n)/2;
		float fk = float(m+n)/2.0;
		float fk2 = float(k);
		if(fk != fk2)
		{
			return vab[k];
		}
		return double(vab[k-1] + vab[k]) / 2.0;
	}

这就没有利用的原理两个数列是已经排序好的特点了，所以需要优化一下。

就是利用截断法原理，每次递归截断一定元素。

本题目就是选取两个数列的中间k/2个元素，要很小心选取这个元素，要诀就是：不要截去的太快了，不然结果就会不正确的。如果截去太快了，就要-1，截去慢一点。看看下面的程序就知道了。

这里有程序查找任意数列中的第K大元素：http://blog.csdn.net/kenden23/article/details/14645619

不同的是这里要利用好原数列特点。

double findMedianSortedArrays(int A[], int m, int B[], int n) {
		int mn = m + n;
		if (0 == mn % 2) 
		{
			return (selectKthNum(A, m, B, n, mn/2-1) + selectKthNum(A, m, B, n, mn/2)) / 2.0;
		} 
		else 
		{
			return selectKthNum(A, m, B, n, mn/2);
		}
	}

	double selectKthNum(int A[], int m, int B[], int n, int k)
	{
		if (m > n) return selectKthNum(B, n, A, m, k);
		if (0 >= m) return B[k];
		if (0 >= n) return A[k];
		if (0 == k) return min(A[0], B[0]);

		int a = min(k/2, m-1);
		int b = k - a - 1;//这里不是k-a，是为了不要截得太快了，不然会出错。
		if (A[a] < B[b]) 
		{
			return selectKthNum(A + a + 1, m - a - 1, B, n, k - a - 1);
		} 
		else 
		{
			return selectKthNum(A, m, B + b +1, n - b -1, k - b -1);
		}
	}

也可以像这样处理下标：

double findMedianSortedArrays3(int A[], int m, int B[], int n) {
		int mn = m + n;
		if (0 == mn % 2) 
		{
			return (selectKthNum(A, m, B, n, mn/2-1) + selectKthNum(A, m, B, n, mn/2)) / 2.0;
		} 
		else 
		{
			return selectKthNum(A, m, B, n, mn/2);
		}
	}

	double selectKthNum(int A[], int m, int B[], int n, int k)
	{
		if (m > n) return selectKthNum(B, n, A, m, k);
		if (0 >= m) return B[k];
		if (0 >= n) return A[k];
		if (0 == k) return min(A[0], B[0]);

		int a = min((k-1)/2, m-1);//这里一定要k-1，否则截去太快了，结果会出错。
		if (A[a] < B[a]) 
		{
			return selectKthNum(A + a + 1, m - a - 1, B, n, k - a - 1);
		} 
		else 
		{
			return selectKthNum(A, m, B + a +1, n - a -1, k - a -1);
		}
	}

所以要理解这里的截去原理！

下标处理很麻烦，看看下面LeetCode论坛上的下标处理也许处理的更加好：

class Solution {
public:
	double findMedianSortedArrays(int A[], int m, int B[], int n) {
		int total = m + n;
		if (0 == total % 2) {
			return (FindKth(A, m, B, n, total/2) + FindKth(A, m, B, n, total/2 + 1)) / 2;
		} else {
			return FindKth(A, m, B, n, total/2 + 1);
		}
	}

	double FindKth(int A[], int m, int B[], int n, int k) {
		if (m > n) return FindKth(B, n, A, m, k);
		if (0 == m) return B[k-1];
		if (0 == n) return A[k-1];
		if (1 == k) return min(A[0], B[0]);

		int aMid = min(k/2, m);
		int bMid = k - aMid;
		if (A[aMid-1] < B[bMid-1]) {
			return FindKth(A + aMid, m - aMid, B, n, k - aMid);
		} else {
			return FindKth(A, m, B + bMid, n - bMid, k - bMid);
		}
	}
};

也可以用查找一般第K大的数的程序完成这道题，也是可以通过的：

double findMedianSortedArrays(int A[], int m, int B[], int n) 
	{
		vector<int> vab(A, A+m);
		for (int i = 0; i < n; i++)
		{
			vab.push_back(B[i]);
		}

		int k = (m+n)/2;
		float fk = float(m+n)/2.0;
		float fk2 = float(k);
		double d1;
		if(fk != fk2)
		{
			d1 = selectKthNumRand(vab, 0, vab.size()-1, k+1);
			return d1;
		}
		int k1 = k+1;
		d1 = selectKthNumRand(vab, 0, vab.size()-1, k1);
		double d2   = selectKthNumRand(vab, 0, vab.size()-1, k);
		return double(d1+d2) / 2.0;
	}

	int selectKthNumRand(vector<int> &vi, int low, int up, int k)
	{
		int mIndex;

		//注意这里会有几率是up=0， low=0，所以要作特殊处理
		if(up-low != 0)
			mIndex = rand()%(up-low) + low;
		else mIndex = 0;
		int mNum = vi[mIndex];

		vector<int> vec1, vec2, vec3;
		for (int i = low; i <= up; i++)
		{
			if(vi[i] > mNum) vec3.push_back(vi[i]);
			if(vi[i] == mNum) vec2.push_back(vi[i]);
			if(vi[i] < mNum) vec1.push_back(vi[i]);
		}

		if(vec1.size()>=k) 
			return selectKthNumRand(vec1, 0, vec1.size()-1, k);
		else if(vec1.size()+vec2.size()>=k) 
			return mNum;
		else if(vec1.size()+vec2.size()<k) 
			return selectKthNumRand(vec3, 0, vec3.size()-1, k-vec1.size()-vec2.size());
	}

2014-1-23 update继续重写更新，其实是很简单的一个二分法的灵活运用：

	double findMedianSortedArrays(int A[], int m, int B[], int n) 
	{
		int k = (m+n)>>1;
		if ((m+n)%2) return findKthElement(A, m, B, n, k+1); 
		return (findKthElement(A, m, B, n, k)+findKthElement(A, m, B, n, k+1))/2;
	}

	double findKthElement(int A[], int m, int B[], int n, int k)
	{
		if (m==0) return B[k-1];//if (!A) return B[k-1];这样写居然是会编译错误的
		if (n==0) return A[k-1];//if (B==NULL) return A[k-1];
		if (k==1) return A[0]<B[0]? A[0]:B[0];

		int mid = (k>>1);
		mid = min(min(m,mid),n);
		k -= mid;
		if (A[mid-1] < B[mid-1])
			return findKthElement(A+mid, m-mid, B, n, k);
		else return findKthElement(A, m, B+mid, n-mid, k);
	}