【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】中位数(暴力+最大最小堆)
题目: """ 对给定长度为N的非负整数序列A,计算前奇数项的中位数。 输入:首行表示序列长度N。次行为N个正整数A1至AN。 输出:输出共(N1)/2行(向下取整),第i行表示到第A1...2i-1项…...
Avro 如何生成java Bean
作为一种很犀利的序列化的格式,avro在大数据量传输的时候很有优势。记录下。 1: .avsc 文件 {"namespace": "com.avro.bean","type": "record","name": "UserBehavior3","fields&qu…...
EG4003-一颗为微波、红外信号放大及处理输出的数模混合芯片
产品描述: EG4003是一款特意为微波、红外信号放大及处理输出的数模混合芯片,内部集成了运算放大器、双门限电压比较器、参考电压源、延时时间定时器和封锁时间定时器及状态控制器等,专用于防盗报警系统、人体门控制装置、照明控制开关等场合。…...
kafka生产者源码精华总结
kafka的源码阅读起来思路很清晰,命名也很规范。 KafkaProducer值得学习的地方: Kafka的网络部分的设计绝对是一个亮点,Kafka基于NIO封装了一套自己的网络架构,支持一个客户端与多个Broker建立连接。处理拆包和粘包的思路和代码&…...
边界缩小维护最值——倒序枚举/中部切开:1101T2
http://cplusoj.com/d/senior/p/CPNOIPB 发现维护边界缩小类最值很难做,有两种常见方法: 倒序进行,边界就变成扩大了在 m i d mid mid 处切开,复杂度可以均摊...
vue实现购物车案例
要求 可以进行购物车水果删除可以进行水果数量增减可以进行总价计算、购物车商品计算选中所有水果也会一同勾选全选框,全选框勾选也能选中所有水果可以记录购物车状态,当页面关闭后重新打开可以看到原先的购物车数据 功能代码 <!DOCTYPE html>…...
工业4G路由器桥接多网络,提升工业环境网络覆盖
一款专为工业环境应用所设计的物联网通讯设备“工业4G路由器”,它具有多种功能和特性。其中之一就是桥接功能,在工业领域中被广泛应用并起着重要的通信作用。 桥接功能是指工业4G路由器通过无线网络的方式,为不同的工业设备提供网络并将其连…...
docker 存储目录迁移
参考:【Docker专题】WSL镜像包盘符迁移详细笔记 - 掘金 docker迁移 一 默认目录 Windows版本(Windows 10 wsl 2)docker 默认程序安装到c盘,数据存放于 C:\Users\当前用户名\AppData\Local\Docker\wsl\data\ext4.vhdx 这样会导致…...
Yolo-Z:改进的YOLOv5用于小目标检测
目录 一、前言 二、背景 三、新思路 四、实验分析 论文地址:2112.11798.pdf (arxiv.org) 一、前言 随着自动驾驶汽车和自动驾驶赛车越来越受欢迎,对更快、更准确的检测器的需求也在增加。 虽然我们的肉眼几乎可以立即提取上下文信息,即…...
系列八、Spring IOC有哪些扩展点,在什么时候调用
一、概述 Spring IOC的扩展点是指IOC在加载过程中,如何对即将要创建的bean进行扩展。 二、扩展点 2.1、实现BeanDefinitionRegistryPostProcessor 调用invokeBeanFactoryPostProcessors时,通过实现BeanDefinitionRegistryPostProcessor接口进行扩展。 …...
《AI时代架构师修炼之道:ChatGPT让架构师插上翅膀》
本专注于帮助架构师在AI时代 实现晋级、提高效率的图书 书中介绍了如何使用 ChatGPT 来完成架构设计的各个环节 并通过实战案例展示了ChatGPT在实际架构设计中的应用方法 关键点 1.架构设计新模式:让架构设计更高效、更快捷、更完美。 2.全流程解析:涵盖…...
git命令清单
一、设置和配置 1.初始化一个新的仓库: git init2.克隆(Clone)一个远程仓库到本地: git clone <repository_url>3.配置用户信息: git config --global user.name "Your Name" git config --global…...
使用Nokogiri和OpenURI库进行HTTP爬虫
目录 一、Nokogiri库 二、OpenURI库 三、结合Nokogiri和OpenURI进行爬虫编程 四、高级爬虫编程 1、并发爬取 2、错误处理和异常处理 3、深度爬取 总结 在当今的数字化时代,网络爬虫已经成为收集和处理大量信息的重要工具。其中,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,验证是否删除干净 whereis python # 安装依赖 yum -y install zlib-devel bzip2-devel openssl-devel ncurses-de…...
《TCP/IP详解 卷一:协议》第5章的IPv4数据报的IHL字段解释
首先说明一下,这里并不解释整个IPv4数据报各个字段的含义,仅仅针对IHL字段作解释。 我们先看下IPv4数据报格式 对于IHL字段, 《TCP/IP详解 卷一:协议》这么解释: IPv4数据报。头部大小可变,4位的IHL字段…...
想去银行的背完这些软件测试面试题,你就稳了...
前言 最近呢有很多的小伙伴问我有没有什么软件测试的面试题,由于我之前一直在忙工作上的事情,没有时间整理面试题,刚好最近休息了一下,顺便整理了一些面试题,现在就把整理的面试题分享给大家,废话就不多说…...
目标检测(Object Detection): 你需要知道的一些概念
文章目录 NMS 非极大值抑制目的步骤 mAP(Mean Average Precision)步骤 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 接口,该接口提供了一些 CURD 及控制事务的方法,另外还可以通过 SqlSession 先获取 Mapper 接口的实例,然后通过 Mapper 接口执行 SQL,Mapper 接口方法的执行最终还是委托到 SqlSe…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
