每天一道剑指offer-数据流的中位数

出自：http://www.zhenganwen.top

已获授权

数据流的中位数 题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

1. public void Insert(Integer num) {

3. }

5. public Double GetMedian() {

7. }

由于中位数只与排序后位于数组中间的一个数或两个数相关，而与数组两边的其它数无关，因此我们可以用一个大根堆保存数组左半边的数的最大值，用一个小根堆保存数组右半边的最小值，插入元素 O(logn)，取中位数 O(1)。

1. public class Solution {

3. //小根堆、大根堆

4. PriorityQueue<Integer> minHeap = new PriorityQueue(new MinRootHeadComparator());

5. PriorityQueue<Integer> maxHeap = new PriorityQueue(new MaxRootHeadComparator());

6. int count = 0;

8. class MaxRootHeadComparator implements Comparator<Integer>{

9. //返回值大于0则认为逻辑上i2大于i1（无关对象包装的数值）

10. public int compare(Integer i1, Integer i2){

11. return i2.intValue() - i1.intValue();

12. }

13. }

15. class MinRootHeadComparator implements Comparator<Integer>{

16. return i1.intValue() - i2.intValue();

17. }

18. }

20. count++;//当前这个数是第几个进来的

21. //编号是奇数就放入小根堆（右半边），否则放入大根堆

22. if(count % 2 != 0){

23. //如果要放入右半边的数比左半边的最大值要小则需调整左半边的最大值放入右半边并将当前这个数放入左半边，这样才能保证右半边的数都比左半边的大

24. if(maxHeap.size() > 0 && num < maxHeap.peek()){

25. maxHeap.add(num);

26. num = maxHeap.poll();

27. }

28. minHeap.add(num);

29. }else{

30. if(minHeap.size() > 0 && num > minHeap.peek()){

31. num = minHeap.poll();

32. }

33. }

34. }

36. if(count == 0){

37. return 0.0;

38. }

39. if(count % 2 != 0){

40. return minHeap.peek().doubleValue();

41. }else{

42. return (minHeap.peek().doubleValue() + maxHeap.peek().doubleValue()) / 2;

43. }

44. }

45. }