如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
数据范围：数据流中数个数满足 
，大小满足 
进阶： 空间复杂度%20%5C)
， 时间复杂度 %20%5C)
进阶： 空间复杂度
[编程题]数据流中的中位数
import java.util.*;
public class Solution {
public PriorityQueue<Integer> stream = new PriorityQueue<>();
public void Insert(Integer num) {
stream.add(num);
}
public Double GetMedian() {
// 1.将公共堆复制到临时堆
PriorityQueue<Integer> temp = new PriorityQueue<>(stream);
// 2.计算堆的size与奇偶
int size = temp.size();
if (size == 0) {
return 0.0;
}
int count = size / 2;
if (size % 2 == 0) {
count--;
}
// 3.依次从堆中弹出元素，找到或计算出中位数
double cur = 0.0;
while (count-- >= 0) {
cur = temp.poll();
}
if (size % 2 == 0) {
cur = (cur + temp.poll()) / 2;
}
return cur;
}
}
发表于 2024-09-03 11:53:01
回复(0)
public class Solution {
ArrayList<Integer> list = new ArrayList<>();
int median=0;
public void Insert(Integer num) {
int s =0,e=list.size()-1;
while(s<=e){
int m = (s+e)/2;
if(num < list.get(m)){
e = m-1;
}else{
s = m+1;
}
}
list.add(s,num);
}
public Double GetMedian() {
System.out.println(list);
if(list.size() % 2 == 1){
return list.get(list.size()/2) * 1.0;
}else{
return (list.get(list.size()/2) + list.get(list.size()/2-1))/2.0;
}
}
}
发表于 2024-08-31 23:39:41
回复(0)
import java.util.*;
public class Solution {
ArrayList<Integer> nums = new ArrayList<>();
public void Insert(Integer num) {
nums.add(num);
nums.sort((a, b)-> a - b);
}
public Double GetMedian() {
int n = nums.size();
if (n % 2 != 0) {
return (double) nums.get(n / 2);
} else {
return (nums.get(n / 2 - 1) + nums.get(n / 2)) / 2.0;
}
}
}
发表于 2024-08-07 17:35:22
回复(0)
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)
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)
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)
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)
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
回复(1)
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)
堆排序和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)
数据流的中位数
由于是数据流，所以需要实时性，用大顶堆与小顶堆。
需要维护使得排序后中间两个数分别在大顶堆和小顶堆的根节点。
排序后，左半边小的需要在大顶堆，大顶堆根节点正好是左半边最大的；
右半边大的需要在小顶堆，小顶堆根节点正好是右半边最小的。（满足求中位数的条件）
大顶堆的最大值（根节点）小于小顶堆的最小值（根节点）。
一个一个添加。如果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)
问题信息
难度：
112条回答
2454收藏
112000浏览
通过挑战的用户
查看代码-
2023-03-11 17:27:26
-
2023-02-26 23:20:51 -
2023-02-03 22:59:46
-
2023-01-06 17:16:22
-
2022-12-12 18:30:08
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
