题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
|
import java.util.*; /* 方法一： public class Solution { ArrayList<Integer> list=new ArrayList<>(); public void Insert(Integer num) { list.add(num); }
public Double GetMedian() { Collections.sort(list); int size=list.size(); double s; if(size%2==0){ s= ((double)list.get(size/2-1)+(double)list.get(size/2))/2; }else s= list.get(size/2);
return s; }
} */ |
方法二：
作者用到的方法非常巧妙，注意到我们只需要位于中间的两个数就可以得出中位数，当元素个数为奇数个时可以看成这两个数一样。中位数在前半部分它是最大的，右半部分是最小的。我们只要始终知道前半部分数里的最大的那个数，后半部分里那个最小的数就可以了，其他的不用关心。这明显是堆的功用，前半部分用一个最大堆，后半部分建一个最小堆。中位数要保持两个堆的数目之差不超过1.为了实现平均分配，可以在数据的总数目是偶数时把新数据插入到最小堆中，否则插入最大堆中。
另一个问题是保持最大堆的所有数据都小于最小堆中的数据。如果总数目和为偶数，根据之前的原则应该插入最小堆中，但是新插入的元素可能比最大堆中的元素小怎么办？这就违反了最小堆的数据一定大于最大堆得原则。实际上这里插入的元素应该是新元素和最大堆中所有元素的最大值，最大堆正好有返回一个最大值的作用，所以新插入的元素先插入最大堆，然后取出最大值再插入最小堆中。如果总数目和为奇数，处理方法类似。
/**
思路：中位数就是数据前一部分的最后一个（最大值）和后半部分的第一个（最小值）的平均。当元素个数为奇数个时可以看成这两个数一样
这里使用两个堆，一个大根堆，保存前半部分数据，小根堆保存后半部分数据。小根堆数据大于大根堆
为了实现平均分配，可以在数据的总数目是偶数时把新数据插入到最小堆中（此时总数+1），否则插入最大堆中。这样也保证了两个堆的数目相差不超过1
最后的结果就是：如果总数是偶数个时，就是小根堆的最小值和大根堆的最大值的平均。
如果是奇数个时，因为添加最后一个元素之前是偶数个，所以会将最后一个添加到小根堆中，所以返回小根堆最小值。
注意：在新插入一个数据时，假设之前总数是偶数，根据自定义规则，这时会将新元素加入到小根堆中，但是此时不能保证此元素会比大根堆的数据大。
所以此时加入小根堆的是新元素和大根堆所有元素的最大值，而不是新元素
同理，如果当前总数是奇数，就会将新元素和小根堆所有元素的最小值加入大根堆。
*/
public class Solution {
/*
java中默认的堆是小根堆,要实现大根堆可以自己设置比较方式
*/
int count=0;
PriorityQueue<Integer> minQue=new PriorityQueue<>();
PriorityQueue<Integer> maxQue=new PriorityQueue<Integer>(11,new Comparator<Integer>(){
public int compare(Integer o1,Integer o2){
return o2-o1;
}
});
public void Insert(Integer num) {
/*
当当前数据总数为偶数时，将新元素和大根堆所有元素的最大值加入小根堆。
当当前数据总数为奇数时，将新元素和小根堆所有元素的最小值加入大根堆。
*/
if(count%2==0){
maxQue.offer(num);
minQue.offer(maxQue.poll());
}else{
minQue.offer(num);
maxQue.offer(minQue.poll());
}
count++;
}
public Double GetMedian() {
if(count%2==0){
return new Double((minQue.peek()+maxQue.peek()))/2;
}else
return new Double(minQue.peek());
}
}