题目大意：
数据流的中位数
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) – 从数据流中添加一个整数到数据结构中。
- double findMedian() – 返回目前所有元素的中位数。
示例：
addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2
进阶:
- 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
- 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=295
解题思路分析：
本题虽然是Hard级别，但是难度并不大，这里分享两种解法。
解法一：二分查找
我们先建立一个List集合，用于存放所有输入的数字，通过addNum方法向list中插入数字时，使用二分查找的方式找到插入下标，以保证数组中的所有数字按照升序排列。findMedian方法中，判断当前list的数据个数，当为奇数时直接返回下标为list.size()/2的中位数，为偶数时返回下标为 list.size()/2 以及 list.size()/2 -1 数字和的一半即可。
实现代码：
// 记录所有输入过的数字
List<Integer> list = new ArrayList<>();
public MedianFinder() {
}
public void addNum(int num) {
// 二分查找当前数字应插入的位置，保证list内元素升序排列
int left=0,right=list.size()-1;
while(left<=right){
int mid = (left+right)/2;
if(list.get(mid)==num){
left=mid;
break;
}else if(list.get(mid)<num){
left=mid+1;
}else{
right=mid-1;
}
}
list.add(left,num);
}
public double findMedian() {
// 找到list的中间数返回
if(list.size()==0) return 0;
int mid=list.size()/2;
if(list.size()%2==0){
return (list.get(mid)+list.get(mid-1))/2.0;
}else{
return list.get(mid);
}
}本解法执行时间为79ms。
Runtime: 79 ms, faster than 32.78% of Java online submissions for Find Median from Data Stream.
Memory Usage: 67 MB, less than 52.54% of Java online submissions for Find Median from Data Stream.
解法二：PriorityQueue （heap）
本解法要使用到两个PriorityQueue。原则上只要我们能将所有数字分成2组，2组的元素个数最多相差为1，并且保证其中一组元素中的数字都大于等于另外一组元素，那么我们很容易在两组数中找到符合条件的中位数。
解题时，建立两个 PriorityQueue 定义为smallHalf和largeHalf，分别代表较小的一半数字与较大的另一半数字。其中smallHalf设定为降序排列，largeHalf为升序排列，插入数据时，当 smallHalf 与 largeHalf 的元素个数相同时，我们向 smallHalf 插入当前数字，插入后，由于要保证 smallHalf 中的元素都小于等于 largeHalf 中的元素，所以我们需要将 smallHalf 中最大的一个元素移动到 largeHalf 中。
当 smallHalf 与 largeHalf 的元素个数不同时，我们向 largeHalf 插入当前元素，同时还需要将 largeHalf 中最小的元素移动到 smallHalf 中。
findMedian方法中，判断 smallHalf 与 largeHalf 的元素个数是否相同，相同时，从 smallHalf 取一个最大值，并从 largeHalf 取一个最小值，求平均数返回即可。如果 smallHalf 的元素个数大于 largeHalf，直接返回 smallHalf 中最大元素，反之返回 largeHalf 中最小元素。
实现代码：
PriorityQueue<Integer> smallHalf = new PriorityQueue<>((a,b)->b-a);
PriorityQueue<Integer> largeHalf = new PriorityQueue<>();
/** initialize your data structure here. */
public MedianFinder() {
}
public void addNum(int num) {
if(smallHalf.size()==largeHalf.size()){
smallHalf.offer(num);
largeHalf.offer(smallHalf.poll());
}else{
largeHalf.offer(num);
smallHalf.offer(largeHalf.poll());
}
}
public double findMedian() {
if(smallHalf.size()==largeHalf.size()){
return (smallHalf.peek()+largeHalf.peek())/2.0;
}else if(smallHalf.size()>largeHalf.size()){
return smallHalf.peek();
}else{
return largeHalf.peek();
}
}本解法执行时间为72ms。
Runtime: 72 ms, faster than 61.58% of Java online submissions for Find Median from Data Stream.
Memory Usage: 58.6 MB, less than 98.31% of Java online submissions for Find Median from Data Stream.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-295-find-median-from-data-stream-解题思路分析/