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