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

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:7minHeap:  5# or maxHeap:5minHeap:  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 indexint 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 arrayMedianInArray 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 elementsMedianInArray(){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 insertiondata[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 worksnewArray[i]=data[i];}data=newArray;}void print(){for(int i=0;i<size;i++){System.out.print(data[i]+" ");}}}}

1 楼 neyshule 2012-06-13   严重支持！ 2 楼 neyshule 2012-06-14   第一种解法扩号不对称啊，是内部类吗？ 3 楼 neyshule 2012-06-14   neyshule 写道第一种解法扩号不对称啊，是内部类吗？
I'm wrong, it's correct, two inner class you mean.

查看更多 下一篇