首页 > 试题广场 >

数据流中的中位数

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

热度指数：430841 时间限制：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 "

算法知识视频讲解

牛客题解官

发表于 2020-06-02 11:00:03

精华题解描述这是一篇针对初学者的题解，共用三种方法解决，从暴力算法到最优算法。知识点：排序，堆难度：二星题解题目描述：对动态数据流求中位数。方法一：暴力方法对于一组数据，我们可以用vector<int> arr来存取。如果对vector排好序，则很容易求出中位数。如果vector的大展开全文

牛客题解官

发表于 2022-04-22 12:20:35

精华题解题目主要信息：寻找数据的中位数数据量在不断输入增长举一反三：学习完本题的思路你可以解决如下题目： BM46. 最小的k个数方法一：插入排序法（推荐使用）知识点：插入排序插入排序是排序中的一种方式，一旦一个无序数组开始排序，它前面部分就是已经排好的有序数组（一开始长度为0），而其后半展开全文

幸福的火龙果在干饭

发表于 2021-07-08 14:55:48

精华题解一、题目描述 JZ63 数据流中的中位数题目大意：设计一个类，它有两个方法，Insert(num)可以插入一个数num，GetMedian()返回所有插入的数中的中位数（若一共插入了偶数个，则取中间两个数的平均值；若一共插入了奇数个，则取中间一个即可）二、算法1（暴力法）解题思路用一个数组来存展开全文

AaroninMind

发表于 2020-02-09 17:46:44

数据流中的中位数首先按照我们的尝试，中位数奇数正好前后对半，取出来即可。偶数呢，前后难以对半，只能折中，取靠近中间的两个数之和求均值。没错，这一题也是如此。但是如何动态的求均值呢。如何在任意时刻都能够直接拿到我们想要的均值而不去计算下标取值呢？百思不得其解。参考他人的想法，使用优先队列Prio 展开全文

Ironxin

发表于 2020-04-23 20:32:40

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

常喝水

发表于 2019-12-23 21:00:01

利用两个堆：用于存储输入数字中较小一半的最大堆（最大堆中的所有数字都小于或等于最大堆的top元素）用于存储输入数字的较大一半的最小堆（最小堆中的所有数字都大于或等于最小堆的顶部元素）只要这两个堆是平衡的（即这两个堆的数量相等或相差1），那么中位数就可以通过这两个堆的堆顶元素获得具体解释可以展开全文

一叶浮尘

发表于 2020-03-20 22:29:47

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

牛客6094022号

发表于 2020-02-10 15:28:22

PriorityQueue<Integer> highQueue = new PriorityQueue<>(); // 小顶堆保存大数据部分展开全文

稚园

发表于 2020-12-15 21:37:57

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

wuqg5518

发表于 2021-10-17 08:58:48

import java.util.ArrayList; import java.util.Collections; public class Solution { ArrayList<Integer> list = new ArrayList<>();//创建一个数展开全文

jack_kuo

发表于 2021-12-01 16:26:38

1.维护两个堆：一个大顶堆放在左边：left，一个小顶堆放在右边：right。 2.每次新进数据的时候更新一下堆，保持两个堆数量动态平衡。 3.每次取中间数的时候，看两个堆的总数量，如果是奇数：那么取大顶堆的根，这个数字是左边最大的。如果是偶数，那么取两个堆的根的平均数，因为大顶堆是左边最大的，小顶展开全文