JAva-Google面接問題-中数を抽出しやすいデータ構造を設計
11285 ワード
ネット上でこの問題の解答を探したが、すべて構想を提供し、具体的な実現を提供しなかった.その中で大きさの山を使うという考え方は簡単そうに見えますが、実現するには多くのことを考えなければなりません.
以下は、ソート配列とサイズスタックでそれぞれ実現します.
サイズヒープの使用:
ソート配列を使用するには:
以下は、ソート配列とサイズスタックでそれぞれ実現します.
サイズヒープの使用:
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]+" ");
}
}
}
}