BM48 数据流中的中位数

àì夳堔傛蜴生んèń 2023-10-04 17:47 39阅读 0赞

### 描述 ###

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

数据范围：数据流中数个数满足1≤n≤1000 ，大小满足 1≤val≤1000  
  
进阶： 空间复杂度 \\O(n) ， 时间复杂度 O(nlogn)

### 示例1 ###

输入：

[5,2,3,4,1,6,7,0,8]

返回值：

"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "

说明：

数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...

### 示例2 ###

输入：

[1,1,1]

返回值：

"1.00 1.00 1.00 "

## 方法一（暴力排序求解） ##

排序方法用的是插入排序

维护一个顺序数组，如果来一个数就与当前的数组的右边进行比较，插入适当位置

import java.util.*;
    public class Solution {
        ArrayList<Integer> list =new ArrayList<>();
        public void Insert(Integer num) {
    //         list.add(num);
    //         Collections.sort(list);  //或者调用库函数直接排序
            if(list.size()==0){   //如果list为空
                list.add(num);   //list是存储已经排好的顺序序列
                return;
            }
            int i;
            for(i=list.size()-1;i>=0;i--){
              if(list.get(i)<num){  //如果list当前的元素大于num，list插入元素不需要移动后面元素
                  list.add(i+1,num);  //则把他放置到该list元素的前面，保证顺序序列
                  return;
              }
            }
            //此时i=-1
            list.add(i+1,num);    //说明该list全部大于num，则把num放到list最前面,不需要移动元素，已经封装好了
        }
    
        public Double GetMedian() {
            if(list.size()%2==1){
                int t=list.size()/2;
                Double d=list.get(t)/1.0;
                return d;
            }
            else{
                int t=list.size()/2;
                Double d=(list.get(t)+list.get(t-1))/2.0;
                return d;
            }
        }
    
    
    }

## 方法二（一个大根堆和一个小根堆） ##

堆排序，大顶堆和小顶堆才是最优算法

（堆排序）  
让数组的前半部分为大顶堆，需要最大值。后半部分为小顶堆，需要最小值  
偶数是两边数目一样，取大顶堆的最大值和小顶堆的最小值的平均  
奇数时，使右边边数目多一个，直接取小顶堆的最小值即可  
由于左边的所有值都小于右边的。所以想往左边插入，则需先插入到右边的小顶堆，之后再弹出个最小的加到左边。反之亦然

import java.util.PriorityQueue;
    import java.util.Comparator;
    public class Solution {
        PriorityQueue<Integer> min_heap=new PriorityQueue<>();
        PriorityQueue<Integer> max_heap=new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return o2-o1;//默认是小顶堆，o1-o2
            }
        });
        int count=0;//记录已获取数字的个数
        public void Insert(Integer num) {
            if(count%2==0){
                max_heap.offer(num);
                int tmp=max_heap.poll();
                min_heap.offer(tmp);
            }
            else{
                min_heap.offer(num);
                int tmp=min_heap.poll();
                max_heap.offer(tmp);
            }
            count++;
        }
    
        public Double GetMedian() {
            if(count%2==0){
                return new Double(min_heap.peek()+max_heap.peek())/2;
            }
            else{
                return new Double(min_heap.peek());
            }
        }
    
    
    }