Google面试题
股市上一个股票的价格从开市开始是不停的变化的，需要开发一个系统，给定一个股票，它能实时显示从开市到当前时间的这个股票的价格的中位数（中值）。
SOLUTION 1:
1.维持两个heap,一个是最小堆，一个是最大堆。
2.一直使maxHeap的size大于minHeap.
3. 当两边size相同时，比较新插入的value,如果它大于minHeap的最大值，把它插入到minHeap。并且把minHeap的最小值移动到maxHeap。
...具体看代码
/**************************************************************
*
* 08-722 Data Structures for Application Programmers
* Lab 7 Heaps and Java PriorityQueue class
*
* Find median of integers using Heaps (maxHeap and minHeap)
*
* Andrew id: yuzhang
* Name: Yu Zhang
*
**************************************************************/ import java.util.*; public class FindMedian {
private static PriorityQueue<Integer> maxHeap, minHeap; public static void main(String[] args) { Comparator<Integer> revCmp = new Comparator<Integer>() {
@Override
public int compare(Integer left, Integer right) {
return right.compareTo(left);
}
}; // Or you can use Collections' reverseOrder method as follows.
// Comparator<Integer> revCmp = Collections.reverseOrder(); maxHeap = new PriorityQueue<Integer>(, revCmp);
minHeap = new PriorityQueue<Integer>(); addNumber();
addNumber();
addNumber();
addNumber();
addNumber();
System.out.println(minHeap);
System.out.println(maxHeap);
System.out.println(getMedian()); addNumber();
System.out.println(minHeap);
System.out.println(maxHeap);
System.out.println(getMedian()); addNumber();
addNumber();
System.out.println(minHeap);
System.out.println(maxHeap);
System.out.println(getMedian());
} /*
* Note: it maintains a condition that maxHeap.size() >= minHeap.size()
*/
public static void addNumber(int value) {
if (maxHeap.size() == minHeap.size()) {
if (minHeap.peek() != null && value > minHeap.peek()) {
maxHeap.offer(minHeap.poll());
minHeap.offer(value);
} else {
maxHeap.offer(value);
}
} else {
if (value < maxHeap.peek()) {
minHeap.offer(maxHeap.poll());
maxHeap.offer(value);
} else {
minHeap.offer(value);
}
}
} /*
* If maxHeap and minHeap are of different sizes,
* then maxHeap must have one extra element.
*/
public static double getMedian() {
if (maxHeap.isEmpty()) {
return -;
} if (maxHeap.size() == minHeap.size()) {
return (double)(minHeap.peek() + maxHeap.peek())/;
} else {
return maxHeap.peek();
}
}
}
SOLUTION 2:
比起solution 1 ，进行了简化
maxHeap保存较小的半边数据，minHeap保存较大的半边数据。
1.无论如何，直接把新值插入到maxHeap。
2. 当minHeap为空，直接退出。
3. 当maxHeap比minHeap多2个值，直接移动一个值到maxHeap即可。
4. 当maxHeap比minHeap多1个值，比较顶端的2个值，如果maxHeap的最大值大于minHeap的最小值，交换2个值即可。
5. 当maxHeap较大时，中值是maxHeap的顶值，否则取2者的顶值的中间值。
/**************************************************************
*
* 08-722 Data Structures for Application Programmers
* Lab 7 Heaps and Java PriorityQueue class
*
* Find median of integers using Heaps (maxHeap and minHeap)
*
* Andrew id: yuzhang
* Name: Yu Zhang
*
**************************************************************/ import java.util.*; public class FindMedian_20150122 {
private static PriorityQueue<Integer> maxHeap, minHeap; public static void main(String[] args) {
// Or you can use Collections' reverseOrder method as follows.
// Comparator<Integer> revCmp = Collections.reverseOrder(); maxHeap = new PriorityQueue<Integer>(, new Comparator<Integer>(){
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}); minHeap = new PriorityQueue<Integer>(); addNumber();
addNumber();
addNumber();
addNumber();
addNumber();
System.out.println(minHeap);
System.out.println(maxHeap);
System.out.println(getMedian()); addNumber();
System.out.println(minHeap);
System.out.println(maxHeap);
System.out.println(getMedian()); addNumber();
addNumber();
System.out.println(minHeap);
System.out.println(maxHeap);
System.out.println(getMedian());
} /*
* Note: it maintains a condition that maxHeap.size() >= minHeap.size()
*/
public static void addNumber1(int value) {
if (maxHeap.size() == minHeap.size()) {
if (!maxHeap.isEmpty() && value > minHeap.peek()) {
// put the new value in the right side.
maxHeap.offer(minHeap.poll());
minHeap.offer(value);
} else {
// add the new value into the left side.
maxHeap.offer(value);
}
} else {
if (value < maxHeap.peek()) {
// add the new value into the left side.
minHeap.offer(maxHeap.poll());
maxHeap.offer(value);
} else {
// add the new value into the right side.
minHeap.offer(value);
}
}
} /*
* Note: it maintains a condition that maxHeap.size() >= minHeap.size()
* solution 2:
*/
public static void addNumber(int value) {
maxHeap.offer(value); // For this case, before insertion, max-heap has n+1 and min-heap has n elements.
// After insertion, max-heap has n+2 and min-heap has n elements, so violate!
// And we need to pop 1 element from max-heap and push it to min-heap
if (maxHeap.size() - minHeap.size() == ) {
// move one to the right side.
minHeap.offer(maxHeap.poll());
} else {
if (minHeap.isEmpty()) {
return;
} // If the newly inserted value is larger than root of min-heap
// we need to pop the root of min-heap and insert it to max-heap.
// And pop root of max-heap and insert it to min-heap
if (minHeap.peek() < maxHeap.peek()) {
// exchange the top value in the minHeap and the maxHeap.
minHeap.offer(maxHeap.poll());
maxHeap.offer(minHeap.poll());
}
}
} /*
* If maxHeap and minHeap are of different sizes,
* then maxHeap must have one extra element.
*/
public static double getMedian() {
if (maxHeap.isEmpty()) {
return -;
} if (maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
} else {
return (double)(maxHeap.peek() + minHeap.peek()) / ;
}
}
}
ref: http://blog.csdn.net/fightforyourdream/article/details/12748781
http://www.ardendertat.com/2011/11/03/programming-interview-questions-13-median-of-integer-stream/
http://blog.sina.com.cn/s/blog_979956cc0101hab8.html
http://blog.csdn.net/ajaxhe/article/details/8734280
http://www.cnblogs.com/remlostime/archive/2012/11/09/2763256.html