题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解题思路
1、简单解法：使用ArrayList存数据
（1）数据插入在ArrayList尾部，在获取中位数时使用Collections进行排序（从源码可以看到实际调用的是Arrays.sort，使用的是归并排序）
时间复杂度为：、时间复杂度：
（2）数据插入时进行排序（二分插入），获取中位数时直接获取
时间复杂度为：、时间复杂度：
注意：如果数据不重复，可以考虑使用排序的TreeSet
//获取中位数时排序
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<Integer> list=new ArrayList<>();
public void Insert(Integer num) {
list.add(num);
}
public Double GetMedian() {
int size=list.size();
if(size==0) return new Double(0);
Collections.sort(list);
return size%2==0?(list.get(size/2)+list.get(size/2-1))*1.0/2.0:new Double(list.get(size/2));
}
}
//插入数据时排序
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> list=new ArrayList<>();
public void Insert(Integer num) {
int size=list.size();
if(size==0||list.get(size-1)<=num) list.add(num);
else{
//使用二分查找
int low=0,high=list.size()-1,mid=0;
while(low<high){
mid=(low+high)/2;
if(list.get(mid)<num) low=mid+1;
else if(list.get(mid)>num) high=mid-1;
else{
low=mid;
break;
}
}
list.add(low,num);
}
}
public Double GetMedian() {
int size=list.size();
return (size&1)==1? new Double(list.get(size/2)) : (list.get(size/2)+list.get(size/2-1))/2.0;
}
}
2、大小堆：使用PriorityQueue
（1）使用两个堆的思想：小顶堆存较大的数，从小到大排序；大顶堆用来存较小的数，从大到小排列；
（2）flag作为标志位，值true时表示数据流中数字的个数为偶数（包括初始值0），为false时表示为奇数（为了防止数据量过大，因而使用boolean而不是int类型来表示）
（3）插入的方法：为了保持两个堆的平衡，因而根据数据流中的数字个数分为奇偶数插入
——若数据流中的数字个数分为奇数，先插入到大顶堆，并将大顶堆中的最大值取出并插入到小顶堆
——若数据流中的数字个数分为偶数，先插入到小顶堆，并将小顶堆中的最小值取出并插入到大顶堆
（4）由于flag初始值为true，因此数据流中的数字个数分为奇数时，大顶堆中的数比小顶堆中的数要多一个，因而这种情况下中位数直接是大顶堆的堆顶元素
时间复杂度为：
、时间复杂度：
import java.util.PriorityQueue;
public class Solution {
//小顶堆存较大的数，从小到大排序；大顶堆用来存较小的数，从大到小排列；
public PriorityQueue<Integer> min=new PriorityQueue<>();//建立小顶堆
public PriorityQueue<Integer> max=new PriorityQueue<>((o1,o2)->o2-o1);//大顶堆
boolean flag=true;//偶数个为true
public void Insert(Integer num) {
if(flag){
min.offer(num);//将num存入小顶堆（里面是较大的数）
max.offer(min.poll());//将小顶堆中的最小值取出存入大顶堆
}else{
max.offer(num);
min.offer(max.poll());
}
flag=flag?false:true;
}
public Double GetMedian() {
return flag? (min.peek()+max.peek())/2.0 : max.peek()*1.0;
}
}
