天天看點

兩個有序數組的中位數

http://blog.csdn.net/hhygcy/article/details/4584064

2個有序數組求合并後的中位數

第一步:假設兩個有序數組(已經各自排序完成了)長度相等,試寫函數找出兩個數組合并後的中位數。 第二步:假設兩個有序數組長度不等,一樣的求出中位數

解析: 這個題目看起來非常簡單。第一題的話: 假設數組長度為n, 那麼我就把數組1和數組2直接合并,然後再直接找到中間元素。對于這樣的方案,第一題和第一題就沒有什麼差別了。這樣的話時間複雜度就是O(n)。通常在這樣的情況下,那些mentor類型的達人就會循循善誘道:“你還有更好的辦法嗎:)” 如果比線性更高效,直接能想到的就是對數了O(log(n)),這個時間複雜度在這裡可能嗎? 當然還是可能的。來繼續看看下面的分析。

先找來了一個圖(自己畫的,簡陋了點)

兩個有序數組的中位數

我們先來分析看看: 想到對數的效率,首先想到的就是二分查找,對于這個題目二分查找的意義在哪裡呢?

我們找到了A[n/2] 和 B[n/2]來比較,

如果他們相等,那樣的話,我們的搜尋結束了,因為答案已經找到了A[n/2]就肯定是排序後的中位數了。

如果我們發現B[n/2]>A[n/2],說明什麼,這個數字應該在 A[n/2]->A[n]這個序列裡面, 或者在 B[1]-B[n/4]這裡面。 或者,這裡的或者是很重要的, 我們可以說,我們已經成功的把問題變成了在排序完成的數組A[n/2]-A[n]和B[0]-B[n/2]裡面找到合并以後的中位數, 顯然遞歸是個不錯的選擇了。

類似的, 如果B[n/2]<A[n/2]呢?顯然就是在A[0]-A[n/2]和B[n/2]-B[n]裡面尋找了。

在繼續想, 這個遞歸什麼時候收斂呢?當然一個case就是相等的值出現, 如果不出現等到這個n==1的時候也就結束了。

照着這樣的思路, 我們比較容易寫出如下的代碼, 當然邊界的值需要自己思量一下, 前面的想法隻是想法而已。

馬上有人說那不定長的怎麼辦呢?一樣的,我們還是來畫個圖看看:(我的畫圖水準肯定提高了)

int find_median_equal_length( int a[], int b[], int length)
{
	if (length == 1) 
		return a[0];	
		
	int i = length/2;
	if (a[i] == b[i])
		return a[i];
	else if (a[i]<b[i])
		return find_median_equal_length( &a[i], &b[0], length-i );
	else 
		return find_median_equal_length( &a[0], &b[i], length-i );
}
           
兩個有序數組的中位數

一樣的, 我們還是把這個兩個數組來比較一下,不失一般性,我們假定B數組比A數組長一點。A的長度為n, B的長度為m。比較A[n/2]和B[m/2] 時候。類似的,我們還是分成幾種情況來讨論:

a. 如果A[n/2] == B[m/2],那麼很顯然,我們的讨論結束了。A[n/2]就已經是中位數,這個和他們各自的長度是奇數或者偶數無關。

b. 如果A[n/2] <   B[m/2],那麼,我們可以知道這個中位數肯定不在[A[0],A[n/2])這個區間内,同時也不在[B[m/2],B[m]]這個區間裡面。這個時候,我們不能沖動地把[A[0],A[n/2])和[B[m/2],B[m]]全部扔掉。我們隻需要把[B[m-n/2],B[m]]和[A[0],A[n/2])扔掉就可以了。(如圖所示的紅色線框),這樣我們就把我們的問題成功轉換成了如何在A[n/2]->A[n]這個長度為n/2的數組和B[1]-B[m-n/2]這個長度為m-n/2的數組裡面找中位數了。問題複雜度即可下降了。

c. 隻剩下A[n/2] > B[m/2],和b類似的,我們可以把A[n/2]->A[n]這塊以及B[1]->B[n/2]這塊扔掉了就行,然後繼續遞歸。

我們也可以寫下如下的代碼:

int find_median_random_length( int a[], int lengtha, int b[], int lengthb)
{
	
	int ma = lengtha/2;
	int nb = lengthb/2;
	int l  = ma <= nb ? ma: nb;
	if (lengtha == 1)
	{
		if (lengthb%2==0)
		{
			if (a[0] >= b[nb])
				return b[nb];
			else if (a[0]<=b[nb-1])
				return b[nb-1];
			return a[0];
		}
		else
			return b[nb];
	}
	else if (lengthb == 1)
	{
		if (lengtha%2==0)
		{
			if (b[0] >= a[ma])
				return a[ma];
			else if (b[0]<=a[ma-1])
				return a[ma-1];
			return b[0];
		}
		else
			return a[ma];
	}
	if ( a[ma] == b[nb] )
		return a[ma];
	else if ( a[ma] < b[nb] )
		return find_median_random_length(&a[ma],lengtha-l,&b[0],lengthb-l);
	else 
		return find_median_random_length(&a[0],lengtha-l,&b[nb],lengthb-l);
}
           

在一些特定的case下面測試了一下,結果還是正确的,下面是用的testcase

int _tmain(int argc, _TCHAR* argv[])
{	
	
	int a[] = {1,2,3,6,8} ;
	int b[] = {6,7,8,9,10};
	std::cout<<"median for equal length is : "<<find_median_equal_length(a, b, sizeof(a)/sizeof(a[0]))<<std::endl; ;
	int c[] = {1,3,5,7,9,11} ;
	int d[] = {2,4,6,8,10,12};

	std::cout<<"median for equal length is : "<<find_median_equal_length(c, d, sizeof(c)/sizeof(c[0]))<<std::endl;;
	
	
	int A[]={1,3,5,7,8,9,10};
	int B[]={2,4,6,10,11,12,13,14,17,19,20};
	int sizeA = sizeof(A)/sizeof(int);
	int sizeB = sizeof(B)/sizeof(int);
	
	std::cout<<"median : "<<find_median_random_length(A,sizeA,B,sizeB)<<std::endl;;
	
	int C[] = {1, 2, 3, 4, 5, 6, 7};
	int D[] = {5, 6, 7, 8, 9};
	std::cout<<"median : "<<find_median_random_length(C,sizeof(C)/sizeof(C[0]),D,sizeof(D)/sizeof(D[0]))<<std::endl;;
	system("pause");
	return 0;
}