首页 > 试题广场 >

数据流中的中位数

[编程题]数据流中的中位数

热度指数：419957 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：数据流中数个数满足 $1 \le n \le 1000 \$ ，大小满足 $1 \le val \le 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 "

算法知识视频讲解

Java

牛客839384289号

PriorityQueue<Integer> max=new PriorityQueue<>();
PriorityQueue<Integer> min=new PriorityQueue<>((m,n)->n-m);
boolean flag=true;
// 大根堆存放小数，且多一个，如果为奇数直接取出即可
public void Insert(Integer num) {
    if(flag){ 
        min.add(num);
        max.add(min.poll());
    }else{
        max.add(num);
        min.add(max.poll());
    }
    flag=!flag;
}

public Double GetMedian() {
    if(max.isEmpty()){
        return 0.0;
    }else if(!flag){
        return max.peek()*1.0;
    }else{
        return (max.peek()+min.peek())*1.0/2;
    }
}

编辑于 2024-03-10 15:43:35 回复(0)

Java

李克雷

public class Solution {

    //小堆存放较大的数据
    PriorityQueue<Integer> heapMin = new PriorityQueue<>();

    //大堆存放较小的数据
    PriorityQueue<Integer> heapMax = new PriorityQueue<>(new Comparator<Integer>() {
        public  int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    public void Insert(Integer num) {
        if (heapMin.size() == heapMax.size()) {
            if (heapMin.peek() != null && num > heapMin.peek()) {
                heapMax.offer(heapMin.poll());
                heapMin.offer(num);
            } else {
                heapMax.offer(num);
            }
        } else {
            if (num < heapMax.peek()) {
                heapMin.offer(heapMax.poll());
                heapMax.offer(num);
            } else {
                heapMin.offer(num);
            }
        }
    }

    public Double GetMedian() {
        if (heapMax.size() == heapMin.size()) {
            return (heapMax.peek() + heapMin.peek()) / 2.0;
        }
        return heapMax.peek() * 1.0;
    }

}

发表于 2023-11-01 15:17:45 回复(0)

Java

你好，泰裤辣

import java.util.*;


public class Solution {

    List<Integer> list = new ArrayList<>();

    public void Insert(Integer num) {
        int index = getIndex(num);
        list.add(index, num);

    }

    public Double GetMedian() {
        int size = list.size();
        if(size % 2 == 0){
            int num1 = list.get(size / 2 - 1);
            int num2 = list.get(size / 2);
            return 1.0 * (num1 + num2) / 2;
        }else{
            return 1.0 * list.get(size / 2);
        }
    }
    // 二分，得到要插入的位置
    public int getIndex(int num){
        int l = 0;
        int r = list.size() - 1;
        int mid = 0;
        while(l <= r){
            mid = l + (r - l) / 2;
            if(list.get(mid) >= num){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
}

发表于 2023-08-27 15:57:12 回复(0)

Java

DDwu

import java.util.*;


public class Solution {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>();
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){
        @Override
        public int compare(Integer o1,Integer o2){
            return o2.compareTo(o1);
        }
    });

    public void Insert(Integer num) {
        minHeap.offer(num);
        maxHeap.offer(minHeap.poll());
        if(minHeap.size()<maxHeap.size()){
             minHeap.offer(maxHeap.poll());
        }
    }
    public Double GetMedian() {
        if(minHeap.size()>maxHeap.size()){
            return (double)minHeap.peek();
        }else{
            return (double )(minHeap.peek()+maxHeap.peek())/2.0;
        }
    }


}

发表于 2023-08-13 17:23:53 回复(0)

Java

做则必成的勇气和信心

public class Solution {
    //堆排序的优先队列
    //大根堆用于升序排序（所以求最小的前k个数用大根堆），小根堆用于降序排序（所以求最大的前k个数
    //用优先队列PriorityQueue 配置大顶堆、小顶堆
    //数组不断增长，每增长一位就排序一次，所以在数据增长时将其有序化
    //中位数，对所有数值排序后，取两个数的平均值
    //中位数：中间数字或中间两个数字的均值
    //也就是说，中位数是较小的一半元素中最大的，并且也是较大的一半元素中最小的
    //通过大根堆得到较小的一半元素中最大的；小根堆得到较小的一半元素中最小的
    //如果是偶数，那就取两个顶顶/2；如果是奇数，那就直接返回任意一个顶。
    PriorityQueue<Integer> max=new PriorityQueue<>();//小顶堆，堆顶最小
    PriorityQueue<Integer> min=new PriorityQueue<>((o1,o2)->o2.compareTo(o1));//大根堆，堆顶最大

    public void Insert(Integer num) {//Insert（）读数据流
        
        min.offer(num);//先加入较小的
        max.offer(min.poll());//将较小部分的最大值取出（删掉），给较大的部分
        if(min.size()<max.size()){   //平衡两个堆的数量
            min.offer(max.poll());
        }
    }

    public Double GetMedian() {//得数据的中位数
       if(min.size()>max.size()){//奇数个
            return (double) min.peek();
       }else{//偶数个
            return (double) (min.peek()+max.peek())/2.0;
       }
    }

发表于 2023-07-21 11:31:24 回复(0)

Java

Hadoopdoop

import java.util.*;
import java.math.BigDecimal;

public class Solution {
    private ArrayList<Integer> list = new ArrayList<Integer>();
    public void Insert(Integer num) {
        list.add(num);
    }
    public Double GetMedian() {
        Collections.sort(list);
        if (list.size() % 2 == 1) {
            return Double.valueOf(list.get(list.size() / 2));
        }
        BigDecimal dc1 = new BigDecimal(list.get(list.size() / 2 - 1));
        BigDecimal dc2 = new BigDecimal(list.get(list.size() / 2));
        BigDecimal divide = dc1.add(dc2).divide(new BigDecimal(2));
        return divide.doubleValue();
    }
}

发表于 2023-03-10 18:19:55 回复(0)

Java

牛暴发

编译器有问题竟然不识别

PriorityQueue

发表于 2022-11-16 19:37:23 回复(0)

Java

程序员大鹏

堆排序和List的默认排序都试了下，结果上看List的排序更快些。

    List<Integer> stream = new ArrayList(8);
    public void Insert(Integer num) {
        stream.add(num);
        Collections.sort(stream);
    }
 
    public Double GetMedian() {
         
        int len = stream.size();
        int middleIndex = len/2;
         
        if(len%2 == 0) {
            return (double)(stream.get(middleIndex) + stream.get(middleIndex-1))/2;
        } else {
            return (double)stream.get(middleIndex);
        }
         
    }

发表于 2022-08-30 22:22:26 回复(0)

Java

624huiguorou

数据流的中位数

由于是数据流，所以需要实时性，用大顶堆与小顶堆。

需要维护使得排序后中间两个数分别在大顶堆和小顶堆的根节点。

排序后，左半边小的需要在大顶堆，大顶堆根节点正好是左半边最大的；

右半边大的需要在小顶堆，小顶堆根节点正好是右半边最小的。（满足求中位数的条件）

大顶堆的最大值（根节点）小于小顶堆的最小值（根节点）。

一个一个添加。如果count为偶数，则先加入大顶堆，然后把大顶堆的根节点放到小顶堆。然后count++，count变为奇数。

如果count为奇数，则先加入小顶堆，然后把小顶堆的根节点放到大顶堆，然后count++，count变为偶数。

当count为奇数时，中位数一定在小顶堆的根节点。当count为偶数时，中位数是大顶堆和小顶堆根节点的平均值。

import java.util.*;


public class Solution {

    //构建一个大顶堆和一个小顶堆
    //大顶堆里最大的值小于小顶堆的最小的值，把两个中位数依次维护到大顶堆的根节点和小顶堆的根节点
    //如果数字个数为奇数，则中位数为小顶堆的根节点。数字为偶数，则中位数为大顶堆和小顶堆根节点的平均值。
    int count = 0;
    
    //默认为小顶堆
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b)->(b-a));
    
    public void Insert(Integer num) {
        //目前是总体是偶数，就先放到大顶堆，然后把大顶堆的根节点放到小顶堆里
        if(count % 2 == 0){
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }else{
            //总体是奇数，就先放到小顶堆，然后把小顶堆的根节点放到大顶堆里，这是最大的
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
        count++;
    }

    public Double GetMedian() {
        //如果总体是偶数，中位数为大顶堆和小顶堆根节点的平均值
        if(count % 2 == 0){
            //Double封装，直接new一个
            return new Double(minHeap.peek() + maxHeap.peek()) / 2;
        }else{
            //如果总体是奇数，中位数为小顶堆的根节点
            return new Double(minHeap.peek());
        }
    }


}

发表于 2022-07-06 11:11:21 回复(0)

Java

MChen-67

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(); // 默认为大根堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

public void Insert(Integer num) {
    if (maxHeap.size() == minHeap.size()) {
        minHeap.add(num * -1);
        maxHeap.add(minHeap.poll() * -1);
    } else {
        maxHeap.add(num);
        minHeap.add(maxHeap.poll() * -1);
    }
}

public Double GetMedian() {
    if (maxHeap.size() == minHeap.size()) {
        if (maxHeap.size() == 0) {
            return 0.0;
        }
        return (double) (maxHeap.peek() + minHeap.peek() * -1) / 2;
    } else {
        return (double) maxHeap.peek();
    }
}

发表于 2022-03-19 17:01:50 回复(0)

Java

nibolyoung

import java.util.*;

public class Solution {
    ArrayList<Integer> list=new ArrayList<>();

    public void Insert(Integer num) {
        list.add(num);
    }

    public Double GetMedian() {
        Collections.sort(list);
        int n=list.size();
        return n%2==0?Double.valueOf((list.get(n/2-1)+list.get(n/2))/2.0):Double.valueOf(list.get(n/2));
    }
}

发表于 2022-03-14 14:29:24 回复(0)

Java

爱学习的小清哥

import java.util.*;
public class Solution {
    ArrayList<Integer> arr = new ArrayList<>();
    public void Insert(Integer num) {
        //插入排序
        if(arr==null) arr.add(num);
        else{
            int i=arr.size()-1;
            while(i>=0&&arr.get(i)>num) i--;
            arr.add(i+1,num);
        }
    }
    public Double GetMedian() {
        if(arr.size()%2 == 0){
            return ((double)arr.get(arr.size()/2)+(double)arr.get((arr.size()/2)-1))/2;
        }else{
            return (double)arr.get(arr.size()/2);
        }
    }
}

发表于 2022-03-11 16:47:05 回复(0)