63 剑指offer---数据流中的中位数
数据流中的中位数
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
int count = 0;
PriorityQueue<Integer> smallHeap = new PriorityQueue<>();
PriorityQueue<Integer> bigHeap = new PriorityQueue<>(15, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
public void Insert(Integer num) {
if(count % 2 ==0){
bigHeap.offer(num);
int maxnum = bigHeap.poll();
smallHeap.offer(maxnum);
}else{
smallHeap.offer(num);
int smallnum = smallHeap.poll();
bigHeap.offer(smallnum);
}
count++;
}
public Double GetMedian() {
if(count %2 ==0){
return (double)((smallHeap.peek()+bigHeap.peek()))/2;
}else {
return (double)(smallHeap.peek());
}
}
}题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
思路
由于数据是从一个数据流中读出来，因而数据的数目随着时间的增加而增加，如果用一个数据容器来保存从流中读出来的数据，则当新的数据从流中读出来的时候，这些数据就插入数据容器。这个数据用什么数据结构定义合适呢？接下来讨论一下最合适的数据结构：
首先，先用一个表格列出可用数据结构的各复杂度
接下来，细细分析一下：
- 数组是最简单的数据容器。如果数组没有排序，那么可以用前面提到的Partition函数找出数组中的中位数。在没有排序的数组中插入一个数字和找出中位数的时间复杂度分别是O（1）和O（n）。
- 在往数组里插入数字的时候我们可以让数组保持排序。这时由于可能需要移动O（n）个数字，因此需要O（n）的时间复杂度。在已排好的数组中取中位数，我们只需要O（1）的时间复杂度即可。
- 排序的链表是另外一种选择，我们需要O（n）的时间复杂度才能在链表中找到其合适的位置插入新的数据。如果定义两个指针指向链表中间的节点，那么可以在O（1）的时间内得出中位数。
- 二叉搜索树可以把插入新数据的平均时间复杂度降低到最低，但是由于二叉搜索树极度不平衡，从而看起来像一个排序的链表的时候，插入新数据的时间仍然是O（n），为了得到中位数，可以在二叉树节点中添加一个表示子树节点数目的字段。有了这个字段，可以在平均O（logN）时间内得到中位数，但最差情况仍然是O（logN）。
- 为了避免二叉搜索树的最差情况，可以利用平衡的二叉搜索树，即VAL树。通常VAL树的平衡因子是左右子树的高度差。可以稍作修改，把VAL树的平衡因子改为左右子树节点数目之差。有了这个改动，可以用O（logN）时间往VAL树中添加一个新节点，同时用O（1）时间得到所有节点的中位数。
- 虽然VAL树的效率很高，但是大部分编程语言的函数库是没有实现这个数据结构的，在面试期间短短几十分钟也是不可能实现这个功能的，所以只能考虑其他办法。
为了保证插入新数据和取中位数的时间效率都高效，这里使用大顶堆+小顶堆的容器，并且满足：
1、两个堆中的数据数目差不能超过1，这样可以使中位数只会出现在两个堆的交接处；
2、大顶堆的所有数据都小于小顶堆，小顶堆的所有数据都大于大顶堆，这样就满足了排序要求。
OK，找出最优的数据结构后，我们再考虑一点细节。首先要保证数据平均分配到两个堆中，因此两个堆中的数据的数目之差不能为1。为了实现平均分配，可以在数据的总数目是偶数的情况下把新数据插入最小堆，否则插入最大堆。
还要保证最小堆的所有数都大于最大堆，因此按照前面的分配规则，会把新的数据插入最小堆。如果此时插入最小堆的数据小于最大堆的最大值，那么它就不能成为最小堆的数据，因此我们需要把这个新数据先插入最大堆，然后取出最大堆里最大值，把最大值插入最小堆中，以此来满足我们的规则——最小堆中所有数字都大于最大堆的数字。同理可插入新数据进入最大堆。
//解法二：使用大堆和小堆的特性
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
private int count = 0;
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
public void Insert(Integer num) {
if (count %2 == 0) {//当数据总数为偶数时，新加入的元素，应当进入小根堆
//（注意不是直接进入小根堆，而是经大根堆筛选后取大根堆中最大元素进入小根堆）
//1.新加入的元素先入到大根堆，由大根堆筛选出堆中最大的元素
maxHeap.offer(num);
int filteredMaxNum = maxHeap.poll();
//2.筛选后的【大根堆中的最大元素】进入小根堆
minHeap.offer(filteredMaxNum);
} else {//当数据总数为奇数时，新加入的元素，应当进入大根堆
//（注意不是直接进入大根堆，而是经小根堆筛选后取小根堆中最大元素进入大根堆）
//1.新加入的元素先入到小根堆，由小根堆筛选出堆中最小的元素
minHeap.offer(num);
int filteredMinNum = minHeap.poll();
//2.筛选后的【小根堆中的最小元素】进入大根堆
maxHeap.offer(filteredMinNum);
}
count++;
}
public Double GetMedian() {
if (count %2 == 0) {
return new Double((minHeap.peek() + maxHeap.peek())) / 2;
} else {
return new Double(minHeap.peek());
}
}
}
代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Solution {
public List<Integer> returnList = new ArrayList<>();
public void Insert(Integer num) {
returnList.add(num);
Collections.sort(returnList);
}
public Double GetMedian() {
if(returnList.size()%2==0){
return (double)(returnList.get(returnList.size()/2)+returnList.get(returnList.size()/2-1))/2;
}else{
if(returnList.size() <= 1){
return (double)returnList.get(0);
}
return (double)returnList.get(returnList.size()/2);
}
}
}
