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