java-谷歌面试题-设计方便提取中数的数据结构

网上找了一下这道题的解答，但都是提供思路，没有提供具体实现。其中使用大小堆这个思路看似简单，但实现起来要考虑很多。
以下分别用排序数组和大小堆来实现。
使用大小堆：

import java.util.Arrays;

public class MedianInHeap {
	/**
	 * 题目：设计方便提取中数的数据结构
	 * 设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度。
	 * 1. 使用排序数组存储。
	 * 插入数字时，在O(logn)时间内找到要插入的位置，在O(n)时间里移动元素并将新数字插入到合适的位置。
	 * 获得中数时，在O(1)复杂度内找到中数。 
	 * 2. 使用大根堆和小根堆存储。
	 * 使用大根堆存储较小的一半数字，使用小根堆存储较大的一半数字。
	 * 插入数字时，在O(logn)时间内将该数字插入到对应的堆当中，并适当移动根节点以保持两个堆数字相等（或相差1）。
	 * 获取中数时，在O(1)时间内找到中数。根据中数的定义，有如下规则：如果两个堆大小相等，则分别取两个堆的根，相加并除以2.
	 * 如果两个堆大小不等（相差1），取元素个数多的那个堆的根，即为中数。
	 * 3.使用二叉查找树--how?
	 */
	
	private MaxHeap maxHeap;
	private MinHeap minHeap;

	public static void main(String[] args) {
		
		MedianInHeap n = new MedianInHeap();
		int[] data={7,9,5,3,1};
		for(int each:data){
			n.add(each);
			System.out.println("median:"+n.median());
			System.out.println("===============");
		}
	}

	public MedianInHeap(){
		maxHeap=new MaxHeap();
		minHeap=new MinHeap();
	}
	
	/*
	 * add an element into 'MedianInHeap'.
	 * However,you need some skill.
	 * Consider [3,5,7,9].The data size is even.Median is (5+7)/2=6.
	 * How do we get '5' and '7'?
	 * Of course we get them from the roots of 'maxHeap' and 'minHeap'.That is fastest.
	 * The problem is ,which is the root of 'maxHeap'?That is,
	 * maxHeap:	7	minHeap:  5		# or maxHeap:	5	minHeap:  7	
	 * 		   /             /		#			   /             /
	 * 		  3             9		#		      3             9
	 * The answer is:'5' is the root of 'maxHeap'.
	 * We use 'maxHeap' to store the smaller part of the data;'minHeap' the bigger.
	 * You are gonna find it yourself.
	 * So,add '1' into 'maxHeap';'6'(or '10') into 'minHeap'.
	 */
	public void add(int item) {
		int sizeMax = maxHeap.size;
		int sizeMin = minHeap.size;
		int rootMax = maxHeap.root();
		int rootMin = minHeap.root();
		if (sizeMax == 0) {
			maxHeap.insert(item);
		} else if (sizeMin == 0) {
			minHeap.insert(item);
		} else {
			if(sizeMax==1&&sizeMin==1&&rootMax>rootMin){//swap to make 'rootMax'<'rootMin'
				int tmp=maxHeap.data[0];
				maxHeap.data[0]=minHeap.data[0];
				minHeap.data[0]=tmp;
			}
			if (item < rootMax) {//insert into 'maxHeap'
				maxHeap.insert(item);
				if (maxHeap.size - minHeap.size > 1) {
					int immigrant = maxHeap.root();
					minHeap.insert(immigrant);
					maxHeap.deleteRoot();
				}
			} else{//insert into 'minHeap'
				minHeap.insert(item);
				if(minHeap.size-maxHeap.size>1){
					int immigrant=minHeap.root();
					maxHeap.insert(immigrant);
					minHeap.deleteRoot();
				}
			}
		}
		System.out.print("max heap:");
		maxHeap.print();
		System.out.print("min heap:");
		minHeap.print();
		//after inserting,size is changed.So update it.
		sizeMax=maxHeap.size;
		sizeMin=minHeap.size;
		int[] allData=new int[sizeMax+sizeMin];
		System.arraycopy(maxHeap.data, 0, allData, 0, sizeMax);//maxHeap.data,not maxHeap,or it will cause "java.lang.ArrayStoreException"
		System.arraycopy(minHeap.data, 0, allData, sizeMax, sizeMin);
		Arrays.sort(allData);
		System.out.println(Arrays.toString(allData));
	}

	public double median() {
		int sizeMax = maxHeap.size;
		int sizeMin = minHeap.size;
		int rootMax = maxHeap.root();
		int rootMin = minHeap.root();
		if(sizeMax==sizeMin){
			return (rootMax+rootMin)/2.0;
		}else{
			return sizeMax>sizeMin?rootMax:rootMin;
		}
	}
	
	class MinHeap {

		int[] data;//maybe we could use ArrayList.
		int size = 0;

		MinHeap() {
			this(10);
		}

		MinHeap(int capacity) {
			data = new int[capacity];
		}

		void print(){
			for(int i=0;i<size;i++){
				System.out.print(data[i]+" ");
			}
			System.out.println();
		}
		
		int root() {
			return data[0];
		}

		void deleteRoot(){
			if(size>1){
				data[0]=data[size-1];
				reheapFromTop(0,size-2);
				size--;
			}
		}
		
		void insert(int item) {
			if (size == 0) {
				data[0] = item;
				size++;
				return;
			}
			if (size == data.length) {
				data = expandHeap(data);
			}
			data[size]=item;
			reheapFromBottom(0,size);
			size++;
		}

		//we use 'int[]' to store heap's data.When you add an element in the end,you should 'reheapFreomBottom'.
		void reheapFromBottom(int begin,int end) {
			int orphan=data[end];
			boolean done = false;
			int curIndex=end;
			int rootIndex = getParent(curIndex);
			while (!done && rootIndex >= 0) {
				if (orphan < data[rootIndex]) {
					data[curIndex] = data[rootIndex];
					curIndex = rootIndex;
					rootIndex = getParent(curIndex);
				} else {
					done = true;
				}
			}
			data[curIndex] = orphan;
		}

		//when you delete the heap's root,you should 'reheapFromTop'.
		void reheapFromTop(int begin,int end) {
			int orphan=data[begin];
			boolean done=false;
			int rootIndex=begin;
			while(!done&&rootIndex<=end){
				int leftIndex=rootIndex*2+1;
				if(leftIndex>end)break;
				int smallIndex=leftIndex;
				int rightIndex=leftIndex+1;
				if(rightIndex<=end&&data[rightIndex]<data[smallIndex]){
					smallIndex=rightIndex;
				}
				if(data[smallIndex]<orphan){
					data[rootIndex]=data[smallIndex];
					rootIndex=smallIndex;
				}else{
					done=true;
				}
			}
			data[rootIndex]=orphan;
		}
	}

	class MaxHeap {

		int[] data;//maybe we could use ArrayList.
		int size = 0;

		MaxHeap() {
			this(10);
		}

		MaxHeap(int capacity) {
			data = new int[capacity];
		}

		int root() {
			return data[0];
		}

		void print(){
			for(int i=0;i<size;i++){
				System.out.print(data[i]+" ");
			}
			System.out.println();
		}
		
		void deleteRoot(){
			if(size>1){
				data[0]=data[size-1];
				reheapFromTop(0,size-2);
				size--;
			}
		}
		void insert(int item) {
			if (size == 0) {
				data[0] = item;
				size++;
				return;
			}
			if (size == data.length) {
				data = expandHeap(data);
			}
			data[size]=item;
			reheapFromBottom(0,size);
			size++;
		}

		void reheapFromBottom(int begin,int end) {
			int orphan=data[end];
			boolean done = false;
			int curIndex=end;
			int rootIndex = getParent(curIndex);
			while (!done && rootIndex >= 0) {
				if (orphan > data[rootIndex]) {
					data[curIndex] = data[rootIndex];
					curIndex = rootIndex;
					rootIndex = getParent(curIndex);
				} else {
					done = true;
				}
			}
			data[curIndex] = orphan;
		}

		void reheapFromTop(int begin,int end) {
			int orphan=data[begin];
			boolean done=false;
			int rootIndex=begin;
			while(!done&&rootIndex<=end){
				int leftIndex=rootIndex*2+1;
				if(leftIndex>end)break;
				int largerIndex=leftIndex;
				int rightIndex=leftIndex+1;
				if(rightIndex<=end&&data[rightIndex]>data[largerIndex]){
					largerIndex=rightIndex;
				}
				if(data[largerIndex]>orphan){
					data[rootIndex]=data[largerIndex];
					rootIndex=largerIndex;
				}else{
					done=true;
				}
			}
			data[rootIndex]=orphan;
		}
	}

	
	//get root's index from a child's index
	int getParent(int curIndex) {
		return (curIndex % 2 == 0) ? (curIndex / 2 - 1) : (curIndex / 2);
	}

	//int[n]-->int[2*n]
	int[] expandHeap(int[] data) {
		int size = data.length;
		int[] newArray = new int[data.length * 2];
		for (int i = 0; i < size; i++) {
			newArray[i] = data[i];
		}
		return newArray;

	}
}

使用排序数组：

public class MedianInSortedArray {

	/**
	 * 题目：设计方便提取中数的数据结构
	 * 设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度。
	 * 1. 使用排序数组存储。
	 * 插入数字时，在O(logn)时间内找到要插入的位置，在O(n)时间里移动元素并将新数字插入到合适的位置。
	 * 获得中数时，在O(1)复杂度内找到中数。 
	 * 2. 使用大根堆和小根堆存储。
	 * 使用大根堆存储较小的一半数字，使用小根堆存储较大的一半数字。
	 * 插入数字时，在O(logn)时间内将该数字插入到对应的堆当中，并适当移动根节点以保持两个堆数字相等（或相差1）。
	 * 获取中数时，在O(1)时间内找到中数。根据中数的定义，有如下规则：如果两个堆大小相等，则分别取两个堆的根，相加并除以2.
	 * 如果两个堆大小不等（相差1），取元素个数多的那个堆的根，即为中数。
	 * 3.使用二叉查找树--how?
	 */
	public static void main(String[] args) {
		//1.Median implemented by sorted array
		MedianInArray m=new MedianInArray();
		for(int i=0;i<12;i++){
			m.insert(i);
			m.print();
			System.out.println(" median is "+m.getMedian());
		}
		
	}

	private static class MedianInArray{
		int[] data;
		int size=0;//record the number of elements
		
		MedianInArray(){
			this(10);
		}
		MedianInArray(int capacity){
			data=new int[capacity];
		}
		
		//like "Insertion Sort"
		void insert(int item){
			if(size==0){
				data[size]=item;
				size++;
			}else{
				if(size+1>data.length){
					expandArray();
				}
				int index=size-1;
				while(index>=0&&data[index]>item){//move backward for insertion
						data[index+1]=data[index];
						index--;
				}
				data[index+1]=item;
				size++;
			}
		}
		
		double getMedian(){
			int mid=size/2;
			if((size &(0x01))==1){
				return data[mid];
			}else{
				return (data[mid]+data[mid-1])/2.0;
			}
			
		}
		
		void expandArray(){
			int capacity=data.length*2;
			int[] newArray=new int[capacity];
			for(int i=0;i<size;i++){//"System.arraycopy" also works
				newArray[i]=data[i];
			}
			data=newArray;
		}
		
		void print(){
			for(int i=0;i<size;i++){
				System.out.print(data[i]+" ");
			}
		}
	}
}

评论

3 楼 neyshule 2012-06-14  

neyshule 写道

第一种解法扩号不对称啊，是内部类吗？

I'm wrong, it's correct, two inner class you mean.

2 楼 neyshule 2012-06-14  

第一种解法扩号不对称啊，是内部类吗？

1 楼 neyshule 2012-06-13  

严重支持！