剑指OfferJZ63：数据流中的中位数-java版

客官°小女子只卖身不卖艺 2023-01-21 03:27 6阅读 0赞

### 剑指OfferJZ63：数据流中的中位数-java版 ###

*   *  jz63:如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
     *   *  采用大顶堆和小顶堆分别维护中位数的左边区间的数和右边区间的数

## jz63:如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。 ##

### 采用大顶堆和小顶堆分别维护中位数的左边区间的数和右边区间的数 ###

如果数据流有偶数个数值，那么中位数为（左区间的最大值+右区间的最小值）/2  
如果数据流有奇数个数值，那么中位数为（左区间的最大值 | 右区间的最小值）（这个可以自定义，哪个区间多一个数就取哪个区间）  
那么采用堆：  
取左区间的最大值就相当于取**大顶堆的堆顶**  
取右区间的最大值就相当于取**小顶堆的堆顶**

import java.util.PriorityQueue;
    public class Solution { 
    //设置两个优先队列(队列:先进先出;优先级队列中，数据按关键词有序排列，插入新数据的时候，会自动插入到合适的位置保证队列有序,默认排序为升序）
        private PriorityQueue<Integer> queue1=new PriorityQueue<>(((o1,o2)->(o2-o1)));//构造大顶堆：中位数的左区间
        private PriorityQueue<Integer> queue2=new PriorityQueue<>();//构造小顶堆：中位数的右区间（优先队列默认构造的是小堆顶，因为每次取出的队顶元素都是最小的，所以也可以new PriorityQueue<>(((o1,o2)->(o1-o2)));）
        private int sum=0;//标记数据流中个数
    
    
        public void Insert(Integer num) { 
            //读取数据流
            if(sum%2==0){ 
                //当两个堆的元素个数一样时，此时新增一个元素，放入大顶堆（左区间）（这样自定义：到时候中位数就取大顶堆堆顶）
                queue1.add(num);//大顶堆
            }else{ 
                queue2.add(num);//小顶堆
            }
            //如果出现大顶堆的堆顶大于小顶堆的堆顶的情况，就将两堆顶互换位置
            if(!queue2.isEmpty() && queue1.peek()>queue2.peek()){ 
                //peek：查询队顶元素
                // poll：删除一个元素，并返回删除的元素
                assert !queue1.isEmpty();//设置assert !queue1.isEmpty();和!queue2.isEmpty()防止空指针报异常
                int temp1=queue1.poll();
                int temp2=queue2.poll();
                queue1.add(temp2);
                queue2.add(temp1);
            }
            sum++;
        }
    
        public Double GetMedian() { 
            //获取当前读取数据的中位数
            if(sum%2==1){ 
                //是奇数，中位数为：大顶堆堆顶
                return (double)queue1.peek();
            }else{ 
                //是偶数，中位数为：（大顶堆堆顶+小顶堆堆顶）/2
                return (double)(queue1.peek()+queue2.peek())/2.0;
            }
        }
    }

![在这里插入图片描述][20210526112543755.gif_pic_center]

[20210526112543755.gif_pic_center]: /images/20221021/fabcd42d9a4046bba620b98b0103c1fb.png