一道经典的Google算法题

      这是一道google的比较经典算法题，题目是：已经两个已经排好序的数组，找出两个数组合起来的中间大的数字。要求算法复杂度尽可能低。如：x数组：1，7，9，10，30    y数组：3，5，8，11    则中间大数为：8

 

     下面是我自己想的算法。 

 

public class GetMiddleValue 
{
	public static void main(String[] args)
	{
		int[] a = {1, 7, 9, 10, 30};
		int[] b = {3, 5, 8, 11};
		
		getMiddleValue(a, b);
		
		getMiddleValue2(a, b);
	}
	
	public static void getMiddleValue(int[] a, int[] b)
	{
		int n = (a.length + b.length + 1)/2;
		
		int i = 0;
		int j = 0;
		int sum = 0;
		int middle = 0;
		boolean flag = true;
		
		while(i < a.length && j < b.length)
		{
			if(a[i] <= b[j])
			{
				i++;
				middle = a[i-1];
			}
			else
			{
				j++;
				middle = b[j-1];
			}
			
			sum++;
			if(sum == n)
			{
				System.out.println("The middle number is : " + middle);
				
				flag = false;
				break;
			}
		}
		
		if(flag)
		{
			if(i == a.length)
			{
				while(sum < n)
				{
					j++;
					sum++;
				}
					
				middle = b[j-1];
			}
			else
			{
				while(sum < n)
				{
					i++;
					sum++;
				}
				
				middle = a[i-1];
			}
			
			System.out.println("The middle number is : " + middle);
		}
	}
	
	public static void getMiddleValue2(int[] a, int[] b)
	{
		int n = (a.length + b.length + 1)/2;
		
		int i = 0;
		int j = 0;
		int middle = 0;
		
		while(i < a.length && j < b.length && n > 0)
		{
			if(a[i] <= b[j])
			{
				i++;
				middle = a[i-1];
			}
			else
			{
				j++;
				middle = b[j-1];
			}
			
			n--;
		}
		
		if(n == 0)
		{
			System.out.println("The middle number is : " + middle);
		}
		else
		{
			if(i == a.length)
			{
				while(n > 0)
				{
					j++;
					n--;
				}
					
				middle = b[j-1];
			}
			else
			{
				while(n > 0)
				{
					i++;
					n--;
				}
				
				middle = a[i-1];
			}
			
			System.out.println("The middle number is : " + middle);		}
	}
}

//算法说明
//若两个数组合并起来有奇数个数，如9个， 则第5个为中间那个数
//若两个数组合并起来有偶数个数，如10个，则第5个为中间那个数

 

评论

5 楼 蔡华江 2010-09-19  

楼主的思路算法应该是最优的，就是怎么写的这么臃肿，还可以优化 

4 楼 tangchj 2010-04-22  

这是我写的算法，看符不符合楼主要求，时间复杂度两数组长度之和
public class Test {

//这是一道google的比较经典算法题，题目是：已经两个已经排好序的数组，
//找出两个数组合起来的中间大的数字。要求算法复杂度尽可能低。
//如：x数组：1，7，9，10，30    y数组：3，5，8，11    则中间大数为：8
//算法说明  
//若两个数组合并起来有奇数个数，如9个， 则第5个为中间那个数  
//若两个数组合并起来有偶数个数，如10个，则第5个为中间那个数 
public static void main(String[] args) {
//int[] a = {1,7,9,10,30};
//int[] b = {3,5,8,11};
// int[] a = {1,2,3};
// int[] b = {4,5,6,7};
int[] a = {1,3,8};
int[] b = {4,5,6,7};
int[] c = new int[a.length+b.length];
int p1 = 0;
int p2 = 0;
for(int i=0;i<a.length+b.length;i++){
if(p1==a.length&&p2<b.length){
while(p2<b.length){
c[i] = b[p2];
i++;
p2++;
}
break;
}
if(p1<a.length&&p2==b.length){
while(p1<a.length){
c[i] = a[p1];
i++;
p1++;
}
break;
}
if(p1>=a.length&&p2>=b.length){
break;
}
if(a[p1]<=b[p2]){
c[i] = a[p1];
p1++;
}else{
c[i] = b[p2];
p2++;
}
}
for(int i=0;i<c.length;i++){
System.out.println(c[i]+",");
}
System.out.println("中间数："+c[(c.length-1)/2]);
}

}

3 楼 jasstion 2009-09-24  

seasun 写道

我的想法是这样的，先得出第一组的中间数，然后再同第二组的数据对比大小

请问有官方答案吗？

你的想法可定不对，第一组的中间数不一定是组合后数据的中间数，你直接在申明一个数据能够存储两个数组，然后对其排序后，不久很容易得到中间的较大的数拉么？

2 楼 yoyo08 2009-07-06  

seasun 写道

我的想法是这样的，先得出第一组的中间数，然后再同第二组的数据对比大小 请问有官方答案吗？

官方答案不知道 你的想法具体怎么样？
假如A={1,2,3}，B={4,5,6,7}，怎么比较？
或者A={1,3,8}，B={4,5,6,7}，又怎么比较？

1 楼 seasun 2009-07-06  

我的想法是这样的，先得出第一组的中间数，然后再同第二组的数据对比大小

请问有官方答案吗？