首页 > 代码库 > Google 面试题：Java实现用最大堆和最小堆查找中位数 Find median with min heap and max heap in Java
Google 面试题：Java实现用最大堆和最小堆查找中位数 Find median with min heap and max heap in Java
Google面试题
股市上一个股票的价格从开市开始是不停的变化的，需要开发一个系统，给定一个股票，它能实时显示从开市到当前时间的这个股票的价格的中位数（中值）。
SOLUTION 1:
1.维持两个heap,一个是最小堆，一个是最大堆。
2.一直使maxHeap的size大于minHeap.
3. 当两边size相同时，比较新插入的value,如果它大于minHeap的最大值，把它插入到minHeap。并且把minHeap的最小值移动到maxHeap。
...具体看代码
1 /************************************************************** 2 * 3 * 08-722 Data Structures for Application Programmers 4 * Lab 7 Heaps and Java PriorityQueue class 5 * 6 * Find median of integers using Heaps (maxHeap and minHeap) 7 * 8 * Andrew id: yuzhang 9 * Name: Yu Zhang10 * 11 **************************************************************/12 13 import java.util.*;14 15 public class FindMedian {16 private static PriorityQueue<Integer> maxHeap, minHeap;17 18 public static void main(String[] args) {19 20 Comparator<Integer> revCmp = new Comparator<Integer>() {21 @Override22 public int compare(Integer left, Integer right) {23 return right.compareTo(left);24 }25 };26 27 // Or you can use Collections‘ reverseOrder method as follows.28 // Comparator<Integer> revCmp = Collections.reverseOrder();29 30 maxHeap = new PriorityQueue<Integer>(20, revCmp);31 minHeap = new PriorityQueue<Integer>(20);32 33 addNumber(6);34 addNumber(4);35 addNumber(3);36 addNumber(10);37 addNumber(12);38 System.out.println(minHeap);39 System.out.println(maxHeap);40 System.out.println(getMedian());41 42 addNumber(5);43 System.out.println(minHeap);44 System.out.println(maxHeap);45 System.out.println(getMedian());46 47 addNumber(7);48 addNumber(8);49 System.out.println(minHeap);50 System.out.println(maxHeap);51 System.out.println(getMedian());52 }53 54 /*55 * Note: it maintains a condition that maxHeap.size() >= minHeap.size()56 */57 public static void addNumber(int value) {58 if (maxHeap.size() == minHeap.size()) {59 if (minHeap.peek() != null && value > minHeap.peek()) {60 maxHeap.offer(minHeap.poll());61 minHeap.offer(value);62 } else {63 maxHeap.offer(value);64 }65 } else {66 if (value < maxHeap.peek()) {67 minHeap.offer(maxHeap.poll());68 maxHeap.offer(value);69 } else {70 minHeap.offer(value);71 }72 }73 }74 75 /*76 * If maxHeap and minHeap are of different sizes, 77 * then maxHeap must have one extra element.78 */79 public static double getMedian() {80 if (maxHeap.isEmpty()) {81 return -1; 82 }83 84 if (maxHeap.size() == minHeap.size()) {85 return (double)(minHeap.peek() + maxHeap.peek())/2;86 } else {87 return maxHeap.peek();88 }89 }90 }
SOLUTION 2:
比起solution 1 ，进行了简化
1.无论如何，直接把新值插入到maxHeap。
2. 当minHeap为空，直接退出。
3. 当maxHeap比minHeap多2个值，直接移动一个值到maxHeap即可。
4. 当maxHeap比minHeap多1个值，比较顶端的2个值，如果maxHeap的最大值小于minHeap的最小值，交换2个值即可。
5. 当maxHeap较大时，中值是maxHeap的顶值，否则取2者的顶值的中间值。
1 /************************************************************** 2 * 3 * 08-722 Data Structures for Application Programmers 4 * Lab 7 Heaps and Java PriorityQueue class 5 * 6 * Find median of integers using Heaps (maxHeap and minHeap) 7 * 8 * Andrew id: yuzhang 9 * Name: Yu Zhang 10 * 11 **************************************************************/ 12 13 import java.util.*; 14 15 public class FindMedian_20150122 { 16 private static PriorityQueue<Integer> maxHeap, minHeap; 17 18 public static void main(String[] args) { 19 // Or you can use Collections‘ reverseOrder method as follows. 20 // Comparator<Integer> revCmp = Collections.reverseOrder(); 21 22 maxHeap = new PriorityQueue<Integer>(20, new Comparator<Integer>(){ 23 public int compare(Integer o1, Integer o2) { 24 return o2 - o1; 25 } 26 }); 27 28 minHeap = new PriorityQueue<Integer>(20); 29 30 addNumber(6); 31 addNumber(4); 32 addNumber(3); 33 addNumber(10); 34 addNumber(12); 35 System.out.println(minHeap); 36 System.out.println(maxHeap); 37 System.out.println(getMedian()); 38 39 addNumber(5); 40 System.out.println(minHeap); 41 System.out.println(maxHeap); 42 System.out.println(getMedian()); 43 44 addNumber(7); 45 addNumber(8); 46 System.out.println(minHeap); 47 System.out.println(maxHeap); 48 System.out.println(getMedian()); 49 } 50 51 /* 52 * Note: it maintains a condition that maxHeap.size() >= minHeap.size() 53 */ 54 public static void addNumber1(int value) { 55 if (maxHeap.size() == minHeap.size()) { 56 if (!maxHeap.isEmpty() && value > minHeap.peek()) { 57 // put the new value in the right side. 58 maxHeap.offer(minHeap.poll()); 59 minHeap.offer(value); 60 } else { 61 // add the new value into the left side. 62 maxHeap.offer(value); 63 } 64 } else { 65 if (value < maxHeap.peek()) { 66 // add the new value into the left side. 67 minHeap.offer(maxHeap.poll()); 68 maxHeap.offer(value); 69 } else { 70 // add the new value into the right side. 71 minHeap.offer(value); 72 } 73 } 74 } 75 76 /* 77 * Note: it maintains a condition that maxHeap.size() >= minHeap.size() 78 * solution 2: 79 */ 80 public static void addNumber(int value) { 81 maxHeap.offer(value); 82 83 // For this case, before insertion, max-heap has n+1 and min-heap has n elements. 84 // After insertion, max-heap has n+2 and min-heap has n elements, so violate! 85 // And we need to pop 1 element from max-heap and push it to min-heap 86 if (maxHeap.size() - minHeap.size() == 2) { 87 // move one to the right side. 88 minHeap.offer(maxHeap.poll()); 89 } else { 90 if (minHeap.isEmpty()) { 91 return; 92 } 93 94 // If the newly inserted value is larger than root of min-heap 95 // we need to pop the root of min-heap and insert it to max-heap. 96 // And pop root of max-heap and insert it to min-heap 97 if (minHeap.peek() < maxHeap.peek()) { 98 // exchange the top value in the minHeap and the maxHeap. 99 minHeap.offer(maxHeap.poll());100 maxHeap.offer(minHeap.poll());101 }102 }103 }104 105 /*106 * If maxHeap and minHeap are of different sizes, 107 * then maxHeap must have one extra element.108 */109 public static double getMedian() {110 if (maxHeap.isEmpty()) {111 return -1;112 }113 114 if (maxHeap.size() > minHeap.size()) {115 return maxHeap.peek();116 } else {117 return (double)(maxHeap.peek() + minHeap.peek()) / 2;118 }119 }120 }
GITHUB: https://github.com/yuzhangcmu/08722_DataStructures/blob/master/08722_LAB7/src/FindMedian_20150122.java
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
Google 面试题：Java实现用最大堆和最小堆查找中位数 Find median with min heap and max heap in Java
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。