数据流中的中位数
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。 ***
思路
这道题想了好多种方法，但都肯定不是最优的。
-
一是没有排序的数组。很容易想到的是用Partition函数找到数组中的中位数。这样一来的话，插入一个数字和找出中位数的时间复杂度是O(1)和O(n)。
-
二是排序的数组。但是插入操作的时间复杂度是O(n)，由于是排好序的数组，所以找到中位数是一个简单的操作，只需要时间复杂度为O(1)。
-
三是排序的链表。需要O(n)时间才能在链表中找到合适的位置插入新的数据。之前我们讨论过采用两个指针指向链表中间结点，那么可以在O(1)时间找到中位数。这样一来，时间效率与基于排序的数组的时间效率是一样的。
-
四是二叉搜索树。可以将把插入新数据的平均时间降到O(nlogn)，但是问题是当二叉搜索树极度不平衡的时候看起来像一个排序的链表，插入新数据的时间将是O(n)。为了得到中位数，可以在二叉树结点中添加一个表示子树结点数目的字段。凭借这个字段，可以在平均时间O(nlogn)时间得到中位数，但最坏的情况仍然需要O(n)时间。
-
五是利用平衡的二叉树，即AVL树。AVL树的平衡因子定义是左右子树的高度差，为找到中位数，我们可以把AVL树的平衡因子定义为左右子树结点数目之差。这样一来可以在O(nlogn)时间内往AVL树添加一个新结点，同时用O(1)时间得到我们需要的中位数。可以说AVL树的效率是最高的，但在短时间内编写其代码不是件容易的事。
然后后来我看了大佬的方法。。emmmmmmm一个最大堆一个最小堆。 偶数情况：先加入min堆，调整之后，再poll出来，加入max堆 奇数情况: 则是相反。 最后返回注意的是奇数的话，中位数在min堆中 真奇妙
Java实现
import java.util.*;
public class Solution {
private PriorityQueue<Integer> min=new PriorityQueue<>();
private PriorityQueue<Integer> max=new PriorityQueue<>(11, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
private int count=0;
public void Insert(Integer num) {
if(count%2==0){
max.offer(num);
min.offer(max.poll());
}
else{
min.offer(num);
max.offer(min.poll());
}
count++;
}
public Double GetMedian() {
if(count%2==0){
return new Double((min.peek()+max.peek()))/2;
}else{
return new Double (min.peek());
}
}
}
