当前位置:首页 > 开发 > 编程语言 > 数据结构 > 正文

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

发表于: 2012-04-12   作者:bylijinnan   来源:转载   浏览:
摘要: 网上找了一下这道题的解答,但都是提供思路,没有提供具体实现。其中使用大小堆这个思路看似简单,但实现起来要考虑很多。 以下分别用排序数组和大小堆来实现。 使用大小堆: import java.util.Arrays; public class MedianInHeap { /** * 题目:设计方便提取中数的数据结构 * 设计一个数据结构,其中包含两个函数,1.插
网上找了一下这道题的解答,但都是提供思路,没有提供具体实现。其中使用大小堆这个思路看似简单,但实现起来要考虑很多。
以下分别用排序数组和大小堆来实现。
使用大小堆:
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