当前位置: 首页 > 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…...

机器学习模型评估中的构念效度:超越基准测试分数的科学推断

1. 项目概述与核心问题在机器学习的日常研究和工程实践中&#xff0c;我们每天都在和各种各样的基准测试&#xff08;Benchmark&#xff09;打交道。无论是为了比较新提出的ResNet变体在ImageNet上的Top-1准确率&#xff0c;还是评估一个大型语言模型在MMLU上的常识推理能力&am…...

Python基础语法:生成器 generator(yield)

一、简介根据指定的规则循环生成数据&#xff0c;当条件不成立时则生成数据结束。数据不是一次性全部生成出来&#xff0c;而是使用一个&#xff0c;再生成一个&#xff0c;好处是可以节约大量的内存。就像设计模式中的懒汉式。适合处理大数据或流数。生成器是一种特殊的迭代器…...

CANoe诊断测试没CDD文件怎么办?手把手教你用Fault Memory窗口和CAPL脚本读取解析DTC故障码

CANoe诊断测试无CDD文件的实战解决方案&#xff1a;从Fault Memory到CAPL脚本全解析当CDD文件缺失或定义不清晰时&#xff0c;诊断测试工程师常常陷入困境。本文将深入探讨如何利用Fault Memory窗口的基础功能&#xff0c;并通过CAPL脚本实现更灵活、更强大的故障码读取与解析方…...

基于随机森林的低成本传感器机器学习校准实践指南

1. 项目概述&#xff1a;当低成本传感器遇上机器学习校准在物联网和智能感知系统铺天盖地的今天&#xff0c;低成本传感器几乎无处不在。从监测办公室的空气质量&#xff0c;到追踪城市街道的噪音污染&#xff0c;再到农业大棚里的温湿度控制&#xff0c;这些价格亲民的“小眼睛…...

Elden Ring帧率解锁终极指南:从60帧到144+的完整教程

Elden Ring帧率解锁终极指南&#xff1a;从60帧到144的完整教程 【免费下载链接】EldenRingFpsUnlockAndMore A small utility to remove frame rate limit, change FOV, add widescreen support and more for Elden Ring 项目地址: https://gitcode.com/gh_mirrors/el/Elden…...

5分钟免费搞定HS2汉化:Honey Select 2完整中文补丁终极教程

5分钟免费搞定HS2汉化&#xff1a;Honey Select 2完整中文补丁终极教程 【免费下载链接】HS2-HF_Patch Automatically translate, uncensor and update HoneySelect2! 项目地址: https://gitcode.com/gh_mirrors/hs/HS2-HF_Patch 还在为Honey Select 2的日文界面而烦恼吗…...

从API调用成功率看Taotoken服务的稳定性与容灾表现

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 从API调用成功率看Taotoken服务的稳定性与容灾表现 在将大模型能力集成到自动化流程或日常开发工具链时&#xff0c;服务的稳定性和…...

CANN runtime:昇腾NPU 运行时的职责边界

个人主页&#xff1a;ujainu 文章目录前言为什么需要运行时这一层runtime管什么&#xff0c;不管什么Stream&#xff1a;并行的基本调度单位Event&#xff1a;跨Stream的同步锚点内存池化&#xff1a;少一次malloc就少一次卡顿任务队列&#xff1a;从计算图到硬件指令的最后一跳…...

地理空间机器学习库全解析:从TorchGeo到Raster Vision的实战指南

1. 项目概述&#xff1a;为什么我们需要专门的地理空间机器学习库&#xff1f;如果你尝试过用标准的PyTorch或TensorFlow去处理一张卫星影像&#xff0c;大概率会在第一步就卡住。不是模型写不出来&#xff0c;而是数据根本读不进去&#xff0c;或者读进去了却对不上位置。一张…...

公共卫生机器学习项目中的算法公平性实践:ACAR框架详解

1. 项目概述&#xff1a;当机器学习遇见公共卫生&#xff0c;公平性为何成为“必答题”&#xff1f;在公共卫生领域&#xff0c;机器学习&#xff08;ML&#xff09;正以前所未有的速度渗透到疾病监测、风险分层和资源分配等核心环节。想象一下&#xff0c;一个模型被用来预测某…...