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

【python】中位数(暴力+最大最小堆)

题目:

"""

对给定长度为N的非负整数序列A,计算前奇数项的中位数。

输入:首行表示序列长度N。次行为N个正整数A1至AN。

输出:输出共(N+1)/2行(向下取整),第i行表示到第A1...2i-1项的中位数。

"""

暴力解法:

n = int(input())

a = list(map(int, input().split()))

b = []

# 遍历输入序列的每个元素

for i in range(1, n + 1):

    # 将当前元素添加到逐步增长的序列中

    b.append(a[i - 1])

    # 对逐步增长的序列进行排序,以便后续找中位数

    b.sort()

    # 当序列长度为奇数时,输出当前的中位数

    if i % 2 == 1:

        print(b[i // 2])

最大+最小堆:

# heapq 模块,它提供了堆操作的基本功能,比如插入元素和删除最小元素。
import heapqn = int(input())
a = list(map(int, input().split()))
# 我们的目标是保持 max_heap 的大小比 min_heap 的大小大1,这样 max_heap 的根节点就是中位数。
# 最大堆用于存储较小的一半数字,最小堆存储较大的一半数字
max_heap, min_heap = [], []for i in range(n):# 将数字加入到堆中# 如果 max_heap 为空或当前数字小于或等于 max_heap 的最大元素(-max_heap[0] 是 max_heap 的最大元素,因为我们用负数来模拟最大堆),则将该数字插入 max_heap。否则,将其插入 min_heap。if not max_heap or a[i] <= -max_heap[0]:heapq.heappush(max_heap, -a[i])else:heapq.heappush(min_heap, a[i])# 保持两个堆的大小平衡# 这两个循环确保了两个堆的大小保持平衡。如果 max_heap 的大小比 min_heap 的大小大2或更多,就从 max_heap 中移除最大元素并将其插入 min_heap。如果 min_heap 的大小比 max_heap 的大小大,就从 min_heap 中移除最小元素并将其插入 max_heap。while len(max_heap) > len(min_heap) + 1:heapq.heappush(min_heap, -heapq.heappop(max_heap))while len(min_heap) > len(max_heap):heapq.heappush(max_heap, -heapq.heappop(min_heap))# 如果当前是奇数项,输出中位数if i % 2 == 0:print(-max_heap[0])

相关文章:

【python】中位数(暴力+最大最小堆)

题目&#xff1a; """ 对给定长度为N的非负整数序列A&#xff0c;计算前奇数项的中位数。 输入&#xff1a;首行表示序列长度N。次行为N个正整数A1至AN。 输出&#xff1a;输出共(N1)/2行&#xff08;向下取整&#xff09;&#xff0c;第i行表示到第A1...2i-1项…...

Avro 如何生成java Bean

作为一种很犀利的序列化的格式&#xff0c;avro在大数据量传输的时候很有优势。记录下。 1&#xff1a; .avsc 文件 {"namespace": "com.avro.bean","type": "record","name": "UserBehavior3","fields&qu…...

EG4003-一颗为微波、红外信号放大及处理输出的数模混合芯片

产品描述&#xff1a; EG4003是一款特意为微波、红外信号放大及处理输出的数模混合芯片&#xff0c;内部集成了运算放大器、双门限电压比较器、参考电压源、延时时间定时器和封锁时间定时器及状态控制器等&#xff0c;专用于防盗报警系统、人体门控制装置、照明控制开关等场合。…...

kafka生产者源码精华总结

kafka的源码阅读起来思路很清晰&#xff0c;命名也很规范。 KafkaProducer值得学习的地方&#xff1a; Kafka的网络部分的设计绝对是一个亮点&#xff0c;Kafka基于NIO封装了一套自己的网络架构&#xff0c;支持一个客户端与多个Broker建立连接。处理拆包和粘包的思路和代码&…...

边界缩小维护最值——倒序枚举/中部切开:1101T2

http://cplusoj.com/d/senior/p/CPNOIPB 发现维护边界缩小类最值很难做&#xff0c;有两种常见方法&#xff1a; 倒序进行&#xff0c;边界就变成扩大了在 m i d mid mid 处切开&#xff0c;复杂度可以均摊...

vue实现购物车案例

要求 可以进行购物车水果删除可以进行水果数量增减可以进行总价计算、购物车商品计算选中所有水果也会一同勾选全选框&#xff0c;全选框勾选也能选中所有水果可以记录购物车状态&#xff0c;当页面关闭后重新打开可以看到原先的购物车数据 功能代码 <!DOCTYPE html>…...

工业4G路由器桥接多网络,提升工业环境网络覆盖

一款专为工业环境应用所设计的物联网通讯设备“工业4G路由器”&#xff0c;它具有多种功能和特性。其中之一就是桥接功能&#xff0c;在工业领域中被广泛应用并起着重要的通信作用。 桥接功能是指工业4G路由器通过无线网络的方式&#xff0c;为不同的工业设备提供网络并将其连…...

docker 存储目录迁移

参考&#xff1a;【Docker专题】WSL镜像包盘符迁移详细笔记 - 掘金 docker迁移 一 默认目录 Windows版本&#xff08;Windows 10 wsl 2&#xff09;docker 默认程序安装到c盘&#xff0c;数据存放于 C:\Users\当前用户名\AppData\Local\Docker\wsl\data\ext4.vhdx 这样会导致…...

Yolo-Z:改进的YOLOv5用于小目标检测

目录 一、前言 二、背景 三、新思路 四、实验分析 论文地址&#xff1a;2112.11798.pdf (arxiv.org) 一、前言 随着自动驾驶汽车和自动驾驶赛车越来越受欢迎&#xff0c;对更快、更准确的检测器的需求也在增加。 虽然我们的肉眼几乎可以立即提取上下文信息&#xff0c;即…...

系列八、Spring IOC有哪些扩展点,在什么时候调用

一、概述 Spring IOC的扩展点是指IOC在加载过程中&#xff0c;如何对即将要创建的bean进行扩展。 二、扩展点 2.1、实现BeanDefinitionRegistryPostProcessor 调用invokeBeanFactoryPostProcessors时&#xff0c;通过实现BeanDefinitionRegistryPostProcessor接口进行扩展。 …...

《AI时代架构师修炼之道:ChatGPT让架构师插上翅膀》

本专注于帮助架构师在AI时代 实现晋级、提高效率的图书 书中介绍了如何使用 ChatGPT 来完成架构设计的各个环节 并通过实战案例展示了ChatGPT在实际架构设计中的应用方法 关键点 1.架构设计新模式&#xff1a;让架构设计更高效、更快捷、更完美。 2.全流程解析&#xff1a;涵盖…...

git命令清单

一、设置和配置 1.初始化一个新的仓库&#xff1a; git init2.克隆&#xff08;Clone&#xff09;一个远程仓库到本地&#xff1a; git clone <repository_url>3.配置用户信息&#xff1a; git config --global user.name "Your Name" git config --global…...

使用Nokogiri和OpenURI库进行HTTP爬虫

目录 一、Nokogiri库 二、OpenURI库 三、结合Nokogiri和OpenURI进行爬虫编程 四、高级爬虫编程 1、并发爬取 2、错误处理和异常处理 3、深度爬取 总结 在当今的数字化时代&#xff0c;网络爬虫已经成为收集和处理大量信息的重要工具。其中&#xff0c;Nokogiri和OpenUR…...

arcpy.message实现探索

arcpy 位置D:\Program Files\GeoScene\Pro\Resources\ArcPy\arcpy\__init__.py ”““AddMessage(消息) 创建可以使用任何GetMessages函数访问的地理处理信息消息(Severity0)。 message(字符串):要添加的消息。”“ arcpy.geoprocessing D:\Program Files\GeoScene\Pro\Re…...

centos卸载自带的Python3.6.8 安装指定的版本号

#卸载python3 rpm -qa|grep python3|xargs rpm -ev --allmatches --nodeps #删除所有残余文件 whereis python3 |xargs rm -frv#查看现有安装的python&#xff0c;验证是否删除干净 whereis python # 安装依赖 yum -y install zlib-devel bzip2-devel openssl-devel ncurses-de…...

《TCP/IP详解 卷一:协议》第5章的IPv4数据报的IHL字段解释

首先说明一下&#xff0c;这里并不解释整个IPv4数据报各个字段的含义&#xff0c;仅仅针对IHL字段作解释。 我们先看下IPv4数据报格式 对于IHL字段&#xff0c; 《TCP/IP详解 卷一&#xff1a;协议》这么解释&#xff1a; IPv4数据报。头部大小可变&#xff0c;4位的IHL字段…...

想去银行的背完这些软件测试面试题,你就稳了...

前言 最近呢有很多的小伙伴问我有没有什么软件测试的面试题&#xff0c;由于我之前一直在忙工作上的事情&#xff0c;没有时间整理面试题&#xff0c;刚好最近休息了一下&#xff0c;顺便整理了一些面试题&#xff0c;现在就把整理的面试题分享给大家&#xff0c;废话就不多说…...

目标检测(Object Detection): 你需要知道的一些概念

文章目录 NMS 非极大值抑制目的步骤 mAP&#xff08;Mean Average Precision&#xff09;步骤 Feature Pyramid Network 特征金字塔结构一阶段检测器Single-Stage Detectors"Anchor-based"的代表RetinaNetAnchor-free 的代表FCOS NMS 非极大值抑制 目的 去除网络输…...

〔001〕虚幻 UE5 发送 get、post 请求、读取 json 文件

✨ 目录 🎈 安装 varest 扩展🎈 开启 varest 扩展🎈 发送 get 请求🎈 发送 post 请求🎈 读取 json 文件🎈 安装 varest 扩展 打开 虚幻商城,搜索 varest 关键字进行检索, varest 是一个 api 调用插件,支持 http/https 请求,也支持 json 文件的读取,最关键是该…...

一条 SQL 是如何在 MyBatis 中执行的

前言 MyBatis 执行 SQL 的核心接口为 SqlSession 接口&#xff0c;该接口提供了一些 CURD 及控制事务的方法&#xff0c;另外还可以通过 SqlSession 先获取 Mapper 接口的实例&#xff0c;然后通过 Mapper 接口执行 SQL&#xff0c;Mapper 接口方法的执行最终还是委托到 SqlSe…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...

Java数组Arrays操作全攻略

Arrays类的概述 Java中的Arrays类位于java.util包中&#xff0c;提供了一系列静态方法用于操作数组&#xff08;如排序、搜索、填充、比较等&#xff09;。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序&#xff08;sort&#xff09; 对数组进行升序…...