LeetCode004----Median of Two Sorted Arrays

問題描述：

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

意即找到2個排序數組合并之後的中位數。條件是複雜度控制在O(log(m+n))，這是本題難點所在！題目難度為HARD，真是名副其實的hard！

思路分析：

剛上來刷Leetcode，這才刷幾道題而已就碰到思路被堵的情況。一上來想着定義一個指針，從小到大一個一個進行比較，進行n/2次循環，即可找到。這樣下來複雜度為O(n/2)，不滿足題目要求。這可是我能想到的最快的方法了。。。。

思路就這樣堵死了！堵死了！堵死了！

重新從頭開始整理思路。第一肯定是需要從中位數的性質入手，第二就是根據要求的複雜度，聯想到肯定是使用二分的思路 采用遞歸的形式進行查找。然而。。。。

思路還是堵死了！堵死了！堵死了！

本來想較勁的，非得自己想出來不可，結果想了2天，草稿紙都換了好幾張了，還是。。。。

思路還是堵死了！堵死了！堵死了！

無奈想先百度中位數的性質，沒想到很快就搜到CSDN了。得到http://blog.csdn.net/zxzxy1988/article/details/8587244，豁然開朗！

思路總結： 

借助于一個尋找2個數組合并後尋找第K小的數的一個算法，這樣求中位數就等于 求第 (nums1Size+nums2Size+1)/2 小的數。（便于說明隻列舉了總個數為奇數的情況，偶數的情況類似，見于代碼）

為什麼采有求第K小的數這個輔助函數呢？因為這樣可以使用二分的思路達到題設要求！我們假設把K一分為二，在2個數組中各找出前K/2個數，做個判斷。如果第一個數組中第K/2個數較小，即nums1[k/2]<nums2[K/2]，那麼可以剔除掉數組一中的前K/2個數，因為他們一定在合并後的數組的前K小的數中，這又是為什麼呢？可以用反證法。證明時需要注意，2個子數組都是有序的！

這樣每次都剔除掉比較小的那部分，把剩下的部分又重新進行遞歸，這次要找的是前 K-（剔除掉的數的個數） 小的數，這樣就可以慢慢的定位到了第K個數。

一共要找K=(m+n)/2個數，每次都是以這種二分的方式進行剔除，每次都近似于剔除掉K/2個數，是以算法複雜度是O( log( (m+n)/2 ) )，滿足要求！

最後AC的代碼如下（20ms）：

int min(int a,int b)
{
	return a<b ? a:b;
}

double findKthNum( int* a, int an, int* b, int bn, int k)
{
	if( an>bn )
		return findKthNum( b, bn, a, an ,k);

	if( an==0)
		return b[k-1];
	if( k==1 )
		return min( a[0],b[0]);

	int p1=min( an, k/2 );
	int p2= k- p1;

	if( a[p1-1] < b[p2-1])
		return findKthNum( a+p1, an-p1, b, bn, k-p1);
	else if( a[p1-1] > b[p2-1])
		return findKthNum( a, an, b+p2, bn-p2, k-p2);
	else
		return a[p1-1];
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
	int size = nums1Size + nums2Size;
	if( size & 1 )
		return findKthNum( nums1, nums1Size, nums2, nums2Size, (size+1 )/2 );
	else
		return 0.5 * ( findKthNum(nums1, nums1Size, nums2, nums2Size, size/2 ) +
			       findKthNum(nums1, nums1Size, nums2, nums2Size, size/2 + 1 ));
}
           

Ps. 當然，這裡給出了由low到進階的多種實作方式：http://blog.csdn.net/hcbbt/article/details/43975275。 這裡又給出了當2個數組長度一樣時的幾種思路：http://www.cnblogs.com/luxiaoxun/archive/2012/09/13/2684054.html。