当前位置: 首页 > news >正文

牛客热题:数据流中的中位数

📟作者主页:慢热的陕西人

🌴专栏链接:力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

在这里插入图片描述

文章目录

  • 牛客热题:数据流中的中位数
    • 题目链接
    • 方法一:直接插入排序
      • 思路
      • 代码
      • 复杂度
    • 方法二:堆
      • 思路
      • 代码
      • 复杂度

牛客热题:数据流中的中位数

题目链接

数据流中的中位数_牛客题霸_牛客网 (nowcoder.com)

方法一:直接插入排序

思路

插入:

  • 对于每次的插入:
    • 如果序列为零:直接插入
    • 如果序列中的值均小于当前要插入的值:直接插入到序列的尾部
    • 找到序列中第一个比当前要插入的值大的位置,然后将当前的值插入到这个位置,将后续的序列向后挪

计算中位数:

  • 对于偶数的情况
    • 我们直接返回第N / 2 和N / 2 - 1 个元素的平均值即可
  • 对于奇数的情况
    • 我们直接返回N / 2个元素

代码

#include <vector>
class Solution {
public:void Insert(int num) {int n = v.size();if(n == 0) {v.push_back(num);return ;}else{auto it = lower_bound(v.begin(), v.end(), num);v.insert(it, num);}}double GetMedian() { int n = v.size();if(n == 1) return v[0];if(n % 2 == 1){return v[n / 2];}else return (v[n / 2] + v[n / 2 - 1]) / 2;}private:vector<double> v;};

复杂度

时间复杂度:O( N 2 N^2 N2) ,因为每次插入都需要在前面的元素中遍历找到对应的位置,所以每个元素的插入的时间复杂度是O(N),因此时间复杂度为O( N 2 N^2 N2)

空间复杂度:O(N) , 只额外使用了一个对应的vector容器来存储

方法二:堆

思路

中位数是指:有序数组中中间的那个数。则根据中位数可以把数组分为如下三段:
[0 ... median - 1], [median], [median ... arr.size() - 1],即[中位数的左边,中位数,中位数的右边]

那么,如果我有个数据结构保留[0…median-1]的数据,并且可以O(1)时间取出最大值,即arr[0...median-1]中的最大值
相对应的,如果我有个数据结构可以保留[median + 1 ... arr.size() - 1] 的数据, 并且可以O(1)时间取出最小值,即
arr[median + 1 ... arr.size() - 1] 中的最小值。
然后,我们把[median]即中位数,随便放到哪个都可以。

假设[0 ... median - 1]的长度为l_len, [median + 1 ... arr.sise() - 1]的长度为 r_len.
1.如果l_len == r_len + 1, 说明,中位数是左边数据结构的最大值
2.如果l_len + 1 == r_len, 说明,中位数是右边数据结构的最小值
3.如果l_len == r_len, 说明,中位数是左边数据结构的最大值与右边数据结构的最小值的平均值。

说了这么多,一个数据结构可以O(1)返回最小值的,其实就是小根堆,O(1)返回最大值的,其实就是大根堆。并且每次插入到堆中的时间复杂度为O(logn)

所以,GetMedian()操作算法过程为:

  • 初始化一个大根堆,存中位数左边的数据,一个小根堆,存中位数右边的数据
  • 动态维护两个数据结构的大小,即最多只相差一个

代码

#include <queue>
class Solution {
private:#define SCD static_cast<double>priority_queue<int> min_q;priority_queue<int, vector<int>, greater<int>> max_q;public:void Insert(int num) {//优先插入到对应的大堆min_q.push(num);max_q.push(min_q.top());min_q.pop();if(min_q.size() < max_q.size()){min_q.push(max_q.top());max_q.pop();}        }double GetMedian() { //因为是优先插入大堆的, 所以:min_q >= max_qreturn min_q.size() > max_q.size() ? SCD(min_q.top()) : SCD(min_q.top() + max_q.top()) / 2;}};

复杂度

  • 时间复杂度:Insert函数O( l o g n logn logn),维护堆的复杂度,GetMedian函数O(1),直接访问
  • 空间复杂度:O(n),两个堆的空间,虽是两个,但是一个堆最多 n / 2 n / 2 n/2

相关文章:

牛客热题:数据流中的中位数

&#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;力扣刷题日记 &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 文章目录 牛客热题&#xff1a;数据流中的中位数题目链接方法一…...

JavaScript-JavaWeb

目录 什么是JavaScript? js引入方式 js基础语法 书写语法 变量 数据据类型 运算符 类型转换 流程语句 js函数 js对象 1.Array 2.String 3.JSON js事件监听 什么是JavaScript? ● JavaScript(简称:JS)是一门跨平台、面向对象的脚本语言。是用来控制网页行为的,它能…...

vue组件通讯$parent和$children获取单签组件的⽗组件和当前组件的⼦组件的例子

在 Vue 中&#xff0c;$parent 和 $children 是实例属性&#xff0c;允许你访问组件的父组件和子组件。但是&#xff0c;请注意&#xff0c;这些属性主要用于在开发过程中进行调试和临时访问&#xff0c;并不推荐在正常的组件通信中使用&#xff0c;因为它们破坏了组件的封装性…...

Util和utils

Util FieldStats 这段代码定义了一个名为FieldStats的Java类&#xff0c;位于com.cqupt.software_1.Util包中。它使用了lombok库的Data和AllArgsConstructor注解&#xff0c;这些注解帮助生成了getter、setter、toString等方法&#xff0c;以及包含所有参数的构造函数。类中有…...

拷贝构造、移动构造、拷贝赋值、移动赋值

最近在学习C的拷贝构造函数时发现一个问题&#xff1a;在函数中返回局部的类对象时&#xff0c;并没有调用拷贝构造函数。针对这个问题&#xff0c;查阅了一些资料&#xff0c;这里记录整理一下。 调用拷贝构造函数的三种情况&#xff1a; ① 用一个类去初始化另一个对象时&a…...

Python3 笔记:math模块

要使用 math 函数必须先导入math模块 语法&#xff1a;import math Python math 模块提供了许多对浮点数的数学运算函数。 math 模块下的函数&#xff0c;返回值均为浮点数&#xff0c;除非另有明确说明。 如果需要计算复数&#xff0c;需使用 cmath 模块中的同名函数。 m…...

python -【四】函数

函数 一、函数的基础 函数&#xff1a;是组织好的&#xff0c;可以重复使用的&#xff0c;用来实现特定功能的代码段 语法 def 函数名(入参): return 出参 # 定义函数 def out_hello():print(hello ~~~)# 调用/使用/执行函数 out_hello()练习题 自定义一个函数&#xff0c…...

力扣 5. 最长回文子串 python AC

动态规划 class Solution:def longestPalindrome(self, s):size len(s)maxl 1start 0dp [[False] * size for _ in range(size)]for i in range(size):dp[i][i] Truefor L in range(2, size 1):for i in range(size):j L i - 1if j > size:breakif s[i] s[j]:if L…...

【微机原理及接口技术】可编程计数器/定时器8253

【微机原理及接口技术】可编程计数器/定时器8253 文章目录 【微机原理及接口技术】可编程计数器/定时器8253前言一、8253的内部结构和引脚二、8253的工作方式三、8253的编程总结 前言 本篇文章就8253芯片展开&#xff0c;详细介绍8253的内部结构和引脚&#xff0c;8253的工作方…...

23种设计模式之一— — — —装饰模式详细介绍与讲解

装饰模式详细讲解 一、定义二、装饰模式结构核心思想模式角色模式的UML类图应用场景模式优点模式缺点 实例演示图示代码演示运行结果 一、定义 装饰模式&#xff08;别名&#xff1a;包装器&#xff09; 装饰模式&#xff08;Decorator Pattern&#xff09;是结构型的设计模式…...

2024年2月28日 星期三

2024年2月28日 星期三 农历正月十九 1. 住建部&#xff1a;各城市要做好今明两年住房发展计划&#xff0c;防止市场大起大落。 2. 政协委员赵长龙建议&#xff1a;增加元旦、端午、中秋高速免费&#xff0c;周六日半价。 3. 人民法院案例库开始对社会开放&#xff0c;与中国…...

Java中的super关键字详解

在Java编程中&#xff0c;super关键字是一个非常重要的概念&#xff0c;尤其是在继承和多态的场景中。理解super关键字的使用方法和其背后的机制&#xff0c;对于掌握面向对象编程&#xff08;OOP&#xff09;的基本概念至关重要。本篇博客将详细讲解super关键字的各种用法及其…...

消消乐游戏开发,三消游戏,消除小游戏

消消乐是一款非常受欢迎的休闲消除类游戏&#xff0c;通常也被称为“三消游戏”。这类游戏的主要目标是通过交换和匹配三个或更多相同的物品来清除它们&#xff0c;从而得分并通过关卡。以下是一些消消乐游戏的基本特点和玩法&#xff1a; 基本玩法 交换和匹配&#xff1a;玩…...

三十三、openlayers官网示例Drawing Features Style——在地图上绘制图形,并修改绘制过程中的颜色

这篇讲的是使用Draw绘制图形时根据绘制形状设置不同颜色。 根据下拉框中的值在styles对象中取对应的颜色对象&#xff0c;new Draw的时候将其设置为style参数。 const styles {Point: {"circle-radius": 5,"circle-fill-color": "red",},LineS…...

Vue——事件修饰符

文章目录 前言阻止默认事件 prevent阻止事件冒泡 stop 前言 在官方文档中对于事件修饰符有一个很好的说明&#xff0c;本篇文章主要记录验证测试的案例。 官方文档 事件修饰符 阻止默认事件 prevent 在js原生的语言中&#xff0c;可以根据标签本身的事件对象进行阻止默认事件…...

Go语言GoFly框架快速新增接口/上手写代码

拿到一个新框架大家可能无从下手&#xff0c;因为你对框架设计思路、结构不了解&#xff0c;从而产生恐惧&#xff0c;所以我们框架是通过简单可视化界面安装&#xff0c;安装后即可看到效果&#xff0c;然后点击先点点看各个功能&#xff0c;看现有的功能是怎么写的&#xff0…...

【Vue】v-else 和 v-else-if

作用&#xff1a;辅助v-if进行判断渲染 语法&#xff1a; v-else v-else-if"表达式"PS&#xff1a;需要紧接着v-if使用 示例代码&#xff1a; <body><div id"app"><p v-if"gender 1">性别&#xff1a;♂ 男</p><…...

一致性hash算法原理图和负载均衡原理-urlhash与least_conn案例

一. 一致性hash算法原理图 4台服务器计算hash值图解 减少一台服务3台服务器计算hash值图解 增加一台服务器5台服务器计算hash值图解 二. 负载均衡原理-urlhash与least_conn 2.1.urlhash案例 # urlhash upstream tomcats {hash $requ...

MySQL建库

删除数据库 新建数据库 右键-新建数据库 字符集选中utf8(支持中文) 修改字符集 右键--数据库的属性 将字符集支持的数量变少可以修改...

系统资源监控器工具glances的使用详解

目录 1、glances工具介绍 2、安装方式 3、glances的工具界面说明 4、常用的参数选项 5、常用快捷键说明 1、glances工具介绍 glances可以分析系统的 CPU使用率、内存使用率、内核统计信息和运行队列信息磁盘I/O速度、传输和读/写比率、磁盘适配器网络I/O速度、传输和读/写…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...