学步园

package su.interview;

import utils.com.ArrayLister;

/**
 * 给定两个有序数组，求中位数.
 * @author Toy
 *
 */
public class MiddleNum_01 {

	/**
	 * 二者先合并成有序数组
	 * @param a
	 * @param b
	 * @return 
	 */
	public void midnum_01(int[] a,int[] b){
		System.out.println("method 1");
		int alen=a.length;
		int blen=b.length;
		int[] c=new int[alen+blen];
		int k=0;
		int i=0;
		int j=0;
		
		while(i<alen&&j<blen){
			if(a[i]<=b[j]){
				c[k++]=a[i];
				i++;
			}else{
				c[k++]=b[j];
				j++;
			}
		}
		while(i<alen){
			c[k++]=a[i++];
		}
		while(j<blen){
			c[k++]=b[j++];
		}
		
		ArrayLister.showArr(c);
		if(k%2!=0){
			System.out.println("mid num is: "+c[k/2]);
		}else{
			System.out.println("mid num are: "+c[k/2-1]+" "+c[k/2]);
		}
	}
	/**
	 * 直接先根据长度确定中位数的顺序
	 * @param a
	 * @param b
	 */
	public void midnum_02(int[] a,int[] b){
		System.out.println("method 2");
		int alen=a.length;
		int blen=b.length;
		int[] mids=new int[]{0,0};

		int pos=(alen+blen)/2;
		int temp=0;
		int i=0;
		int j=0;
		int k=0;//为即将插入的位置.
		
		while(i<alen&&j<blen){
			if(a[i]<=b[j]){
				temp=a[i];
				i++;
			}else{
				temp=b[j];
				j++;
			}
			k++;
			int state = checkK(pos,k-1,temp,mids);
			if(state==2){
				break;
			}

		}
		while(i<alen){
			temp=a[i];
			i++;
			k++;
			int state = checkK(pos,k-1,temp,mids);
			if(state==2){
				break;
			}

		}
		while(j<blen){
			temp=b[j];
			j++;
			k++;
			int state = checkK(pos,k-1,temp,mids);
			if(state==2){
				break;
			}
		}
		
		if((alen+blen)%2==0){
			System.out.println("mid num are: "+mids[0]+" "+mids[1]);	
		}else{
			System.out.println("mid num is: "+mids[1]);	
		}

	}
	private int checkK(int pos, int k, int temp, int[] mids) {
//		System.out.println(pos+" "+k+" "+temp);

		if(k==pos-1){
			mids[0]=temp;
			return 1;
		}
		if(k==pos){
			mids[1]=temp;
			return 2;
		}
		if(mids[0]>0&&mids[1]>0){
			return 2;
		}

		return 0;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a=new int[]{1,2,3,4,5,12,13};
		int[] b=new int[]{6,7,8,9,10,29,30};
		
		MiddleNum_01 m=new MiddleNum_01();
		m.midnum_01(a, b);
		m.midnum_02(a, b);
	}
}