中位数

中位数问题：

 

第一题：

给定一个集合，首先该集合为空，之后不断往集合中加入整数，请依次输出每次加入一个整数后，集合里的中位数，请给出你的算法。如下面的例子

集合                 中位数
{1}                       1
{1,2}                    1
{1,2,4}                 2
{1,2,4,7}              2
{1,2,4,7,13}         4

 

思路：

每次插入一个元素，用二分插入法找到其位置，然后取出下标为 n/2的元素作为中位数

 

package org.jyjiao;

import java.util.List;
import java.util.*;

public class Mid1{
	
	List<Integer> list=new ArrayList<Integer>();
	
	int getPosition(int data,int left,int right){
		int p=-1;
		int mid,mid_data;
		while(left<=right){
			mid=(left+right)/2;
			mid_data=list.get(mid).intValue();
			if(data==mid_data){
				p=mid;
				break;
			
			}else if(data>mid_data){
				left=mid+1;
				
				
			}else{
				right=mid-1;
				
			}
		}
		if(left>right){
			p=left;
		}
		return p;
		
	}
	
	public void displayMid(int n){
		int i=0;
		int a;
		while(i<n){
			a=(int)(Math.random()*100);
			if(i==0){
				list.add(a);
				System.out.println(a+":"+list);
			}else{
				int index=getPosition(a,0,list.size()-1);
				if(index==list.size()){
					list.add(new Integer(a));					
				}else{
					int len=list.size();
					list.add(list.get(len-1));
					for(int j=len-1;j>index;j--){
						list.set(j,list.get(j-1));
					}
					list.set(index,new Integer(a));
				}
		        System.out.println(list.get(list.size()/2)+":"+list);
		
			}
				
			i++;
		}
	}
	
	public static void main(String[] args){
		Mid1 m=new Mid1();
		m.displayMid(10);
	}
}

  

 注：这道题用LinkedList, 效率会高很多：

package org.jyjiao;

import java.util.List;
import java.util.*;

public class Mid12{
	
	List<Integer> list=new LinkedList<Integer>();
	
	int getPosition(int data,int left,int right){  //二分插入求新数据的位置
		int p=-1;
		int mid,mid_data;
		while(left<=right){
			mid=(left+right)/2;
			mid_data=list.get(mid).intValue();
			if(data==mid_data){
				p=mid;
				break;
			
			}else if(data>mid_data){
				left=mid+1;
			}else{
				right=mid-1;
			}
		}
		if(left>right){
			p=left;
		}
		return p;
		
	}
	
	public void displayMid(int n){
		int i=0;
		int a;
		while(i<n){
			a=(int)(Math.random()*100);
			if(i==0){
				list.add(a);
				System.out.println(a+":"+list);
			}else{
				int index=getPosition(a,0,list.size()-1);
				/*if(index==list.size()){
					list.add(new Integer(a));					
				}else{
					int len=list.size();
					list.add(list.get(len-1));
					for(int j=len-1;j>index;j--){
						list.set(j,list.get(j-1));
					}
					list.set(index,new Integer(a));
				}
				*/
				list.add(index,new Integer(a));      //改为这样
		        System.out.println(list.get(list.size()/2)+":"+list);
		
			}
				
			i++;
		}
	}
	
	public static void main(String[] args){
		Mid1 m=new Mid1();
		m.displayMid(10);
	}
}

 

-----------------------------------------------------------------------------------------------------------

第二题：

两个有序数组A和B，求归并后的中位数，O（logn）算法

 

思路：

若A和B的长度都为1，则令归并后的中位数为B中的元素
若A和B的长度大于1，用O(1)的复杂度，从A和B中选出各自的中位数，假设为m，n
若m==n,则归并后的中位数仍然为m，结束
若m<n,则保留A中大于等于m的数，B中小于等于n的数，递归，直到m==n，或者某个集合的长度减为1
若m>n，则保留A中小于等于m的数，B中大于等于n的数，递归，停止条件同上。

 

 

package org.jyjiao;

public class Max3 {

	int getMid(int[] array1, int[] array2, int l1, int r1, int l2, int r2) {
		int mid1, mid2, mid_data = -1;
		if (l1 == r1) {
			mid_data = array1[l1];

		} else if (l2 == r2) {
			mid_data = array2[l2];

		} else {
			mid1 = (l1 + r1) / 2;
			mid2 = (l2 + r2) / 2;
			if (array1[mid1] == array2[mid2]) {
				mid_data = array1[mid1];
			} else if (array1[mid1] < array2[mid2]) {
				l1 = mid1;
				r2 = mid2;
				mid_data=getMid(array1, array2, l1, r1, l2, r2);  //注意返回值
			} else {
				r1 = mid1;
				l2 = mid2;
				mid_data=getMid(array1, array2, l1, r1, l2, r2);
			}
		}
		return mid_data;
	}

	public static void main(String args[]) {
		int[] array1 = {1,3,5,7,9,11,13};
		int[] array2 = {2,4,6,8,10,12,16};
		Max3 m=new Max3();
		int mid=m.getMid(array1,array2,0,array1.length-1,0,array2.length-1);
		System.out.println("mid="+mid);

	}

}

 

 

 

-------------------------------------------------------------------------------------------------------------

第三题：求无序数组的中位数：

即求第 n/2大的数，平均复杂度为： n+n/2+n/4+n/8+...=2n

 

package org.jyjiao;

public class Mid2 {
		
	int partion(int[] array,int left,int right){
		int index=-1;
		int mid=(left+right)/2;
		int mdata=array[mid];
		array[mid]=array[right];
		array[right]=mdata;
		int i=left,j=right;
		while(i<j){
			while((array[i]<mdata)&&(i<j)){
				i++;
			}
			if(i<j){
				array[j]=array[i];
				j--;
			}
			while(array[j]>mdata&&(i<j)){
				j--;
			}
			if(i<j){
				array[i]=array[j];
				i++;
			}
		}
		
		
		array[i]=mdata;
		index=i;
		System.out.println("i="+i+"j="+j);
		return index;
	}
	
	int getMid(int[] array,int left,int right){
		int ret=-1;
		int mid=(array.length-1)/2;
		while(true){
			ret=partion(array,left,right);
			if(ret==mid){
				ret=mid;
				break;
			}else if(ret<mid){
				left+=1;
			}else{
				right-=1;
			}
		}
		
		return array[ret];		
	}
	
	
	public static void main(String[] args){
		int[] array={1,53,95,7,-19,32,4,56,81,10,22,12};
		Mid2 m=new Mid2();
		int ret=m.getMid(array,0,array.length-1);
		System.out.println("ret="+ret);
	}
	
}

 

 

 变种：http://blog.chinaunix.net/u3/94271/showart_2020121.html