每日OJ题_优先级队列_堆④_力扣295. 数据流的中位数

2024-04-07 05:04

本文主要是介绍每日OJ题_优先级队列_堆④_力扣295. 数据流的中位数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

力扣295. 数据流的中位数

解析代码


力扣295. 数据流的中位数

295. 数据流的中位数

难度 困难

中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。

  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1:

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

  • -10^5 <= num <= 10^5
  • 在调用 findMedian 之前,数据结构中至少有一个元素
  • 最多 5 * 10^4 次调用 addNum 和 findMedian
class MedianFinder {
public:MedianFinder() {}void addNum(int num) {}double findMedian() {}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

解析代码

此题有三个解法,三个解法的find函数的时间复杂度都是O(1)。看看add的时间复杂度:

  • 第一个解法是进来一个数,sort一下,这样add的时间复杂度是O(N*logN)。
  • 第二个解法是插入排序的思想,这样add的时间复杂度是(N)。
  • 第三个解法是用两个堆来维护中位数,这样add的时间复杂度是O(logN)。

第三个解法难想,但是做完这道题以后能想起来就行。这里用第三个解法:

        将整个数组按照大小平分成两部分(如果不能平分,那就让较小部分的元素多⼀个), 较小的部分称为左侧部分,较大的部分称为右侧部分:

        将左侧部分放入大根堆中,然后将右侧元素放入小根堆中,这样就能在 O(1) 的时间内拿到中间的一个数或者两个数,进而求的平均数。

        于是问题就变成了如何将一个一个从数据流中过来的数据,动态调整到大根堆或者小根堆中,并且保证两个堆的元素一致,或者左侧堆的元素比右侧堆的元素多一个。

为了方便叙述,将左侧的大根堆记为 left ,右侧的小根堆记为 right ,数据流中来的数据记为 x 。

其实,就是分类讨论的过程:

  • 如果左右堆的数量相同, left.size() == right.size() :

如果两个堆都是空的,直接将数据 x 放入到 left 中; 如果两个堆非空:

  1. 如果元素要放入左侧,也就是 x <= left.top() :那就直接放,因为不会影响我们制定的规则;
  2. 如果要放入右侧可以先将 x 放入 right 中, 然后把 right 的堆顶元素放入 left 中
  • 如果左右堆的数量不相同。那就是 left.size()  =  right.size() + 1:

这个时候我们关心的是 x 是否会放入 left 中,导致 left 变得过多:

  1. 如果 x 放入 right 中,也就是 x >= right.top() ,直接放。
  2. 反之,就是需要放入 left 中: 可以先将 x 放入 left 中,然后把 left 的堆顶元素放入 right 中。

        只要每一个新来的元素按照上述规则执行,就能保证 left 中放着整个数组排序后的左半部分, right 中放着整个数组排序后的右半部分,就能在 O(1)的时间内求出平均数,且插入的时间复杂度首O(logN)。

class MedianFinder {// 较小的部分称为左侧部分,较大的部分称为右侧部分:// 将左侧部分放入大根堆中,然后将右侧元素放入小根堆中,priority_queue<int> left; // ⼤根堆priority_queue<int, vector<int>, greater<int>> right; // ⼩根堆public:MedianFinder() {}void addNum(int num) {if(left.size() == right.size()){if(right.empty() || left.top() > num){left.push(num);}else{right.push(num);left.push(right.top());right.pop();}}else{if(left.top() > num){left.push(num);right.push(left.top());left.pop();}else{right.push(num);}}}double findMedian() {if(left.size() == right.size())return (left.top() + right.top()) / 2.0;return left.top();}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

这篇关于每日OJ题_优先级队列_堆④_力扣295. 数据流的中位数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881695

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

Linux之进程状态&&进程优先级详解

《Linux之进程状态&&进程优先级详解》文章介绍了操作系统中进程的状态,包括运行状态、阻塞状态和挂起状态,并详细解释了Linux下进程的具体状态及其管理,此外,文章还讨论了进程的优先级、查看和修改进... 目录一、操作系统的进程状态1.1运行状态1.2阻塞状态1.3挂起二、linux下具体的状态三、进程的

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s