第一步：
假设两个有序数组（已经各自排序完成了）长度相等，试写函数找出两个数组合并后的中位数。第二步：假设两个有序数组长度不等，一样的求出中位数。
假设数组长度为n, 那么我就把数组1和数组2直接合并，然后再直接找到中间元素。对于这样的方案，时间复杂度就是O(n)。
public class sortmid{
public static void main(String args[]){
int a[]={1,3,5,7,8,9,15};
int b[]={2,3,4,6,8,32,53,56};
int mid;
sortmid smid=new sortmid();
mid=smid.merge(a,b);
System.out.println("中间数是："+mid);
}
public int merge(int[] a,int[] b){
int c;
c=a.length+b.length;
int hb[]=new int[c];
int x=0;int i=0,j=0;
while(x<c){
if(i<a.length&&j<b.length){
if(a[i]<=b[j])
hb[x++]=a[i++];
else hb[x++]=b[j++];
}
else if(i>=a.length&&j<b.length){
hb[x++]=b[j++];
}
else{
hb[x++]=a[i++] ;
}
}
System.out.println("合并以后：");
for(i=0;i<c;i++)
System.out.print(hb[i]+",");
return hb[c/2];
}
}
我们先来分析看看： 想到对数的效率，首先想到的就是二分查找，对于这个题目二分查找的意义在哪里呢？
我们找到了A[n/2] 和 B[n/2]来比较，如果他们相等，那样的话，我们的搜索结束了，因为答案已经找到了A[n/2]就肯定是排序后的中位数了。
如果我们发现B[n/2]>A[n/2]，说明什么,这个数字应该在 A[n/2]->A[n]这个序列里面， 或者在 B[0]-B[n/2]这里面。 或者，这里的或者是很重要的， 我们可以说，我们已经成功的把问题变成了在排序完成的数组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] > b[0] ? b[0] : 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 );
}
java // int find_median_equal_length( int a[]，int starta, int b[],int startb, int length)
{
if (length == 1)
return a[starta] > b[startb] ? b[startb] : a[starta];
int i = length/2;
if (a[ starta+i] == b[startb+i])
return a[i];
else if (a[ starta+i ]<b[ startb+i ])
return find_median_equal_length( a ,starta+i, b,startb, length-i );
else
return find_median_equal_length( a, starta ,b , startb+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]这块扔掉了就行,然后继续递归。
我们也可以写下如下的代码：
1. int find_median_random_length( int a[], int lengtha, int b[], int lengthb)
2. {
3.
4. int ma = lengtha/2;
5. int nb = lengthb/2;
6. int l = ma <= nb ? ma: nb;
7. if (lengtha == 1)
8. {
9. if (lengthb%2==0)
10. {
11. if (a[0] >= b[nb])
12. return b[nb];
13. else if (a[0]<=b[nb-1])
14. return b[nb-1];
15. return a[0];
16. }
17. else
18. return b[nb];
19. }
20. else if (lengthb == 1)
21. {
22. if (lengtha%2==0)
23. {
24. if (b[0] >= a[ma])
25. return a[ma];
26. else if (b[0]<=a[ma-1])
27. return a[ma-1];
28. return b[0];
29. }
30. else
31. return a[ma];
32. }
33. if ( a[ma] == b[nb] )
34. return a[ma];
35. else if ( a[ma] < b[nb] )
36. return find_median_random_length(&a[ma],lengtha-l,&b[0],lengthb-l);
37. else
38. return find_median_random_length(&a[0],lengtha-l,&b[nb],lengthb-l);
39. }
网友评论