【C++】求第二大的数详细解析
文章目录
- 💯前言
- 💯题目描述
- 💯输入描述
- 💯解题思路分析
- 1. 题目核心要求
- 2. 代码实现与解析
- 3. 核心逻辑逐步解析
- 定义并初始化变量
- 遍历并处理输入数据
- 更新最大值与次大值
- 输出结果
- 4. 示例分析
- 示例输入
- 示例输出
- 数据处理过程
- 💯高级拓展与优化分析
- 时间与空间复杂度
- 潜在错误与改进方向
- 数学与工程意义
- 💯多种解法的对比与讨论
- 排序法
- 分治法
- 💯小结
💯前言
- 在计算机科学和算法设计领域,如何以最优的方式处理有限的资源和数据一直是一个重要的研究课题。针对这一问题,本次探讨围绕一个经典的编程挑战展开:
寻找数列中的次大值
。本题虽然在描述上简洁,但通过限制变量和数据结构的使用,从而将重点放在动态维护状态变量和优化算法性能上。这不仅为基础算法设计提供了宝贵的训练机会,同时也为解决实际工程中的资源约束问题
提供了可借鉴的思路。
本次分析将从题目背景、算法设计、代码实现
、扩展优化及多解法对比等多个角度,系统地探讨这一问题的本质及其实现方法。
C++ 参考手册
💯题目描述
数学里有一个函数定义为 max(a, b)
,它返回 a 和 b 中较大的那个值。基于这一定义,现要求完成一个函数 max2
,旨在从当前已经处理过的所有输入数字中,返回次大值。
需要注意的是,本题对代码实现有如下明确限制:
- 只能使用两个全局变量
a1
和a2
分别记录当前最大值和次大值。 - 不允许使用数组或其他结构存储所有输入的数字。
- 允许额外使用两个局部变量用于存储整数个数 n 和当前输入的整数。
💯输入描述
第一行输入一个整数 n,表示有 n 个正整数满足 2 ≤ n ≤ 100 2 \leq n \leq 100 2≤n≤100。
第二行输入 n 个互不相等的正整数。
输出描述
输出仅包含一个整数,即输入数列中的次大值。
示例1
输入:
10
10 9 8 7 6 5 4 3 2 1
输出:
9
💯解题思路分析
1. 题目核心要求
本题的核心在于从输入数据中以高效方式求解次大值,同时遵守以下条件约束:
- 输入正整数各不相同,保证了最大值和次大值的存在性。
- 只能使用两个变量
a1
和a2
存储结果状态,考验算法设计对空间资源的优化。 - 需要保证算法能够在线性时间内完成计算,即时间复杂度为 O ( n ) O(n) O(n)。
2. 代码实现与解析
以下是问题的完整代码实现:
#include <iostream>
using namespace std;
#include <climits>void max2() {int n;cin >> n; // 读取正整数个数int a1 = INT_MIN; // 最大值初始化为最小整数int a2 = INT_MIN; // 次大值初始化为最小整数for (int i = 0; i < n; ++i) {int num;cin >> num; // 逐一读取每个正整数if (num > a1) {// 当前数字比最大值大,则更新最大值和次大值a2 = a1;a1 = num;} else if (num > a2) {// 当前数字介于最大值和次大值之间,更新次大值a2 = num;}}cout << a2 << endl; // 输出次大值
}int main() {max2();return 0;
}
3. 核心逻辑逐步解析
定义并初始化变量
int a1 = INT_MIN;
int a2 = INT_MIN;
- 目的:
a1
用于记录当前的最大值。a2
用于记录当前的次大值。- 初始化为
INT_MIN
,以确保任何正整数输入都可以覆盖初始值。
遍历并处理输入数据
for (int i = 0; i < n; ++i) {int num;cin >> num;
- 使用
for
循环逐一读取正整数,并对每个输入值进行处理。 - 每次读取到的新数字需要根据与
a1
和a2
的关系进行条件判断。
更新最大值与次大值
if (num > a1) {a2 = a1;a1 = num;
} else if (num > a2) {a2 = num;
}
- 逻辑分析:
- 当
num > a1
时:- 原最大值
a1
退化为次大值a2
。 - 新数字
num
成为新的最大值a1
。
- 原最大值
- 当
num
位于最大值a1
和次大值a2
之间时:- 更新
a2
为当前数字num
。
- 更新
- 当
输出结果
cout << a2 << endl;
- 循环结束后,
a2
中存储的是次大值,直接输出。
4. 示例分析
示例输入
10
10 9 8 7 6 5 4 3 2 1
示例输出
9
数据处理过程
迭代次数 | 当前数字 (num ) | 最大值 (a1 ) | 次大值 (a2 ) |
---|---|---|---|
1 | 10 | 10 | INT_MIN |
2 | 9 | 10 | 9 |
3 | 8 | 10 | 9 |
… | … | … | … |
10 | 1 | 10 | 9 |
最终结果:次大值为 9。
💯高级拓展与优化分析
时间与空间复杂度
- 时间复杂度:
- 对输入数据的单次遍历,复杂度为 O ( n ) O(n) O(n),与数据规模呈线性关系。
- 空间复杂度:
- 仅使用两个额外变量
a1
和a2
,复杂度为 O ( 1 ) O(1) O(1)。
- 仅使用两个额外变量
潜在错误与改进方向
-
初始化问题
- 如果未正确初始化
a1
和a2
,例如初始化为0
,在输入为负数时会导致错误。 - 为避免此类问题,需始终选择合适的初始值,例如
INT_MIN
。
- 如果未正确初始化
-
边界条件处理
- 当 ( n = 2 ) 时,代码需要保证能够正确处理这类极小输入规模的场景。
-
逻辑健壮性
- 对于更复杂的输入场景(如输入中存在重复值或非法值),需增加必要的输入校验逻辑。
数学与工程意义
从数学角度来看,本题的核心问题是动态维护“前两大值”。这类问题在实际工程中有广泛应用,例如:
- 流式数据处理:实时更新数据流的统计特性。
- 排名问题:动态维护某指标的前 k 个最大值。
在资源受限的场景下(如嵌入式设备或内存有限的系统),设计类似的轻量级算法尤为重要。
💯多种解法的对比与讨论
排序法
- 思路:对输入数据排序,取倒数第二个值。
- 时间复杂度: O ( n log n ) O(n \log n) O(nlogn)。
- 缺点:额外的空间和时间开销。
分治法
- 思路:递归分组寻找最大值和次大值。
- 时间复杂度:接近 O ( n ) O(n) O(n)。
- 缺点:代码复杂度较高,且在小规模数据上优势不明显。
💯小结
通过本题,我们可以清晰认识到在有限资源条件下,如何设计高效算法以满足问题需求。这不仅考察了程序的正确性,还着重强调了代码的优化能力和设计美感。
这种能力的培养需要长期的练习和理论积累,同时在不同场景中总结经验。更重要的是,这类问题的解决思路能够拓展到更广泛的工程实践中,例如实时数据分析、大规模流数据处理等领域,为构建更高效的系统打下坚实基础。
相关文章:
【C++】求第二大的数详细解析
博客主页: [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 💯前言💯题目描述💯输入描述💯解题思路分析1. 题目核心要求2. 代码实现与解析3. 核心逻辑逐步解析定义并初始化变量遍历并处理输入数据更新最大值与次大值输…...
Ubuntu18安装后基本配置操作
1. 关掉自动更新 不关掉自动更新,会将你的ubuntu系统更新到更高版本,一些配置就不能用了,所以要关掉自动更新。在“软件和更新”中将“自动检查更新”设置为从不。 2. ubuntu换国内源 参考链接换源 按照这个换源这个换源好使 ,…...
【Azure 架构师学习笔记】- Azure Function (1) --环境搭建和背景介绍
本文属于【Azure 架构师学习笔记】系列。 本文属于【Azure Function 】系列。 前言 随着无服务计算的兴起和大数据环境中的数据集成需求, 需要使用某些轻量级的服务,来实现一些简单操作。因此Azure Function就成了微软云上的一个必不可少的组成部分。 …...
【ubuntu】将Chroma配置为LINUX服务
Chroma是一个轻量级向量数据库。既然是数据库,那么我希望它是能够长时间运行。最直接的方式是配置为service服务。 可惜官方没有去提供配置为服务的办法,而鄙人对docker又不是特别感冒。所以自己研究了下chroma配置为服务的方式。 系统:ubu…...
Linux24.04 安装企业微信
今天工作需要把windows系统换成了linux,但是公司的沟通工具是企业微信。去企业微信官网看了,没有linux版本,只能想办法解决了,不然再换回去就太坑了。 方案 1、使用docker容器,2、使用deepin-wine 本人对docker不太熟…...
路由引入问题(双点双向路由回馈问题)
简介 总所周知,路由引入import又称路由重分发redistribute,为了解决不同路由协议进程间路由信息不互通而使用的技术,由于不同路由协议的算法、机制、开销等因素的差异,它们之间无法直接交换路由信息。因此,路由引入技…...
Redis 实现分布式锁
单实例条件下的分布式锁 -- 加锁操作 -- KEYS[1]: 锁的键(lock_key) -- ARGV[1]: 当前客户端的标识(client_id) -- ARGV[2]: 锁的过期时间(毫秒)if (redis.call(EXISTS, KEYS[1]) 0) then-- 如果锁不存在…...
Redis客户端(Jedis、RedisTemplate、Redisson)
1. 简介 Redis作为一个当下很火热的非关系型数据库,Java从业人员基本都离不开对Redis的使用。在Java程序中该数据库,需要借助于市面上的开源客户端,如Jedis、Spring Data Redis、Redisson,它们可以作为操作Redis非关系型数据库的桥…...
虚幻引擎内各个组件的关系
1. GameMode: 关系: GameMode 是游戏规则的制定者和管理者,GameState 则是游戏状态的记录者和同步者。GameMode 通常负责创建和初始化 GameState。 交互: GameMode 可以直接访问和修改 GameState 的属性,例如更新游戏分数、切换游戏阶段等。GameState 的变化会通过 GameMode …...
Python Flask Web框架快速入门
Flask 入门Demo Flask 开发环境搭建,执行如下指令: pip install flask# 第一节: Flask 快速入门from flask import Flask app Flask(__name__)app.route(/flask) def hello_flask():return Hello Flaskapp.run()核心代码剖析: 从flask包导…...
【java学习笔记】Set接口实现类-LinkedHashSet
一、LinkedHashSet的全面说明 (就是把数组不同位置的链表当成一个节点然后相连)...
阿里云ACP云计算模拟试题(附答案解析)
1、将基础设施作为服务的云计算服务类型是_____服务。 A.laas B.Paas C.SaaS D.Daas 答案:A 解析:基础设施即服务有时缩写为 IaaS,包含云 IT 的基本构建块,通常提供对联网功能、计算机(虚拟或专用硬件&#x…...
java 缓存篇2
缓存的部署方式 单机主从哨兵集群 特性主从(Master-Slave)哨兵(Sentinel)集群(Cluster)数据分片不支持不支持支持,基于 slot 进行水平分片高可用性部分支持(手动故障转移ÿ…...
12.11-12.12总结(约瑟夫问题 机器翻译 滑动窗口)
12.11 刷题 《算法竞赛》这本书看了很多了,但是题目没咋做,所以今天来刷一下题 P1996约瑟夫问题 还依稀记得大一的时候被约瑟夫支配的恐惧(哭),但是现在做就感觉很简单(虽然也敲了一会,今早感…...
Elasticsearch+Kibana+IK分词器+拼音分词器安装
目录 ES报错 Kibanaik分词器拼音分词器 安装都比较简单,可以参考这几篇博客 ES 如何在 Linux,MacOS 及 Windows 上进行安装 Elasticsearch 报错 ES启动报错error downloading geoip database [GeoLite2-ASN.mmdb] Kibana KIBANA的安装教程ÿ…...
2020 年“泰迪杯”数据分析职业技能大赛A 题教育平台的线上课程智能推荐策略
2020 年“泰迪杯”数据分析职业技能大赛A 题教育平台的线上课程智能推荐策略 完整代码请私聊 博主 一、 背景 近年来,随着互联网与通信技术的高速发展,学习资源的建设与共享呈现出新的发展趋势,各种网课、慕课、直播课等层出不穷,…...
运维面试题
1 deployment和statefulset区别 Kubernetes (k8s) 中的 Deployment 和 StatefulSet 是两种不同类型的控制器,用于管理应用的生命周期,但它们适用于不同的应用场景。以下是它们在存储、调度顺序和网络分配方面的区别: 存储 Deployment: 适用…...
计算机网络之网络层超详细讲解
个人主页:C忠实粉丝 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C忠实粉丝 原创 计算机网络之网络层超详细讲解 收录于专栏【计算机网络】 本专栏旨在分享学习计算机网络的一点学习笔记,欢迎大家在评论区交流讨论💌 …...
Windows桌面系统管理2:VMware Workstation使用和管理
Windows桌面系统管理0:总目录-CSDN博客 Windows桌面系统管理1:计算机硬件组成及组装-CSDN博客 Windows桌面系统管理2:VMware Workstation使用和管理 Windows桌面系统管理3:Windows 10操作系统部署与使用-CSDN博客 Windows桌面系统管理4:Windows 10操作系统运维管理-…...
深入理解 CSS 文本换行: overflow-wrap 和 word-break
前言 正常情况下,在固定宽度的盒子中的中文会自动换行。但是,当遇到非常长的英文单词或者很长的 URL 时,文本可能就不会自动换行,而会溢出所在容器。幸运的是,CSS 为我们提供了一些和文本换行相关的属性;今…...
【Linux】Ubuntu:安装系统后配置
hostname:更改主机名 打开终端。 使用hostnamectl命令更改主机名。 sudo hostnamectl set-hostname 新的主机名你可以使用hostnamectl 命令来验证更改是否成功: hostnamectlChrome:更换默认浏览器 以下是从 Ubuntu 中移除预装的 Snap 版 Fi…...
我们来学mysql -- MSI安装(安装篇)
主题 书接上文,在《探讨win安装方式》中官方推荐MSI要是把大厂的标准奉为圭臬,说啥认啥,他一翻脸,小丑不就是咱了再说了,都干到家门口了8.4版本官方文档,还不给他梭罗下 MSI 点击**.msi弹出MySQL Install…...
MySQL其一,概念学习,可视化软件安装以及增删改查语句
目录 MySQL 1、数据库的概念 2、数据库分类 3、MySQL的安装 4、安装过程中的问题 DataGrip的使用: SQLynx的使用: 5、编写SQL语句 6、DDL语句 7、DML 新增数据: 删除数据: 修改数据: MySQL SQL其实是一门…...
SpringCloud 题库
这篇文章是关于 SpringCloud 面试题的汇总,包括微服务的概念、SpringCloud 的组成及相关技术,如服务注册与发现、负载均衡、容错等,还涉及 Nacos 配置中心、服务注册表结构等原理,以及微服务架构中的日志采集、服务网关、相关概念…...
【ETCD】[源码阅读]深度解析 EtcdServer 的 processInternalRaftRequestOnce 方法
在分布式系统中,etcd 的一致性与高效性得益于其强大的 Raft 协议模块。而 processInternalRaftRequestOnce 是 etcd 服务器处理内部 Raft 请求的核心方法之一。本文将从源码角度解析这个方法的逻辑流程,帮助读者更好地理解 etcd 的内部实现。 方法源码 …...
数据分析与机器学习全解析
一、数据分析基础要点 (一)数据收集 确定数据源:明确是内部数据库、外部公开数据、传感器采集还是用户调研等来源,不同来源数据质量与获取难度各异。例如内部销售数据可直接获取,而市场调研数据需设计问卷并投入人力收…...
Qt 一个简单的QChart 绘图
Qt 一个简单的QChart 绘图 先上程序运行结果图: “sample9_1QChart.h” 文件代码如下: #pragma once#include <QtWidgets/QMainWindow> #include "ui_sample9_1QChart.h"#include <QtCharts> //必须这么设置 QT_CHARTS_USE_NAME…...
力扣——322. 零钱兑换
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。 示…...
Qt之网络监测
在Qt中,网络监测通常涉及到检测网络连接状态、网络延迟、带宽使用情况等。Qt提供了一些类和模块来帮助开发者实现这些功能。以下是一些常用的方法和类: 1. 检测网络连接状态 QtNetwork模块中的QNetworkConfigurationManager类可以用来检测设备的网络连…...
抓包软件fiddler和wireshark使用手册
fiddler官方文档 Fiddler 抓包教程1 Fiddler 抓包教程2 wireshark抓包学习 2添加链接描述 ip 过滤 ip.src_host ip.dst_host ip.addr mac 过滤 eth.src eth.dst eth.addr 端口过滤 tcp.port tcp.srcport tcp.dstport 协议类型过滤 arp dhcp 规则组合 and or...
【从零开始入门unity游戏开发之——C#篇03】变量和常量
文章目录 一、变量1、什么是变量?2、申明变量的固定写法3、变量的类型值和引用类型的区别无符号和有符号位——表示变量所占用的内存空间的大小范围——表示变量的取值范围取值范围和存储单位的关系为什么byte的范围是 0 到 255?为什么 sbyte 的范围是 -…...
SpringBoot 手动实现动态切换数据源 DynamicSource (上)
大家好,我是此林。 在实际开发中,经常可能遇到在一个SpringBoot Web应用中需要访问多个数据源的情况。 下面来介绍一下多数据源的使用场景、底层原理和手动实现。 一、 多数据源经典使用场景 场景一:业务复杂,数据量过大 1. 业务…...
ERROR Error: command failed: yarnError: command failed: yarn
1、异常信息 2、解决 解决方法一: WinR进入命令行,重新安装npm(如果报镜像源问题建议镜像源也重新配置) 输入命令,重新安装npm/yarn #npm npm install#npm 配置镜像源 npm config set registry https://registry.npmmirror.com#npm 查看镜…...
【java】finalize方法
目录 1. 说明2. 调用过程3. 注意事项 1. 说明 1.finalize方法是Java中Object类的一个方法。2.finalize方法用于在对象被垃圾回收之前执行一些清理工作。3.当JVM(Java虚拟机)确定一个对象不再被引用、即将被回收时,会调用该对象的finalize方法…...
C++ 内存管理和模板与STL
此篇目是之后各种C库的基础 目录 内存管理 内存分布 内存管理方式 new和delete operator new 与 operator delete函数 实现原理 定位new表达式(placement-new) 模板基础 泛型编程 模板 函数模板 类模板 STL 组成部分 内存管理 内存分布 int globalVar 1; //全局变量 静…...
同一个局域网下的两台电脑实现定时或者实时拷贝数据
【亲测能用】 需求:从数据库服务器上将数据库备份文件*.bak,每天定时拷贝到局域网下另一台电脑上,实现异机备份。 本文中192.168.1.110是本机,192.168.1.130是异机(备份机)。需求是每天定时从192.168.1.1…...
Python毕业设计选题:基于django+vue的汽车租赁管理网站
开发语言:Python框架:djangoPython版本:python3.7.7数据库:mysql 5.7数据库工具:Navicat11开发软件:PyCharm 系统展示 用户管理 汽车品牌管理 汽车信息管理 汽车租赁管理 汽车商品信息管理 汽车租赁 购物…...
scrapy对接rabbitmq的时候使用post请求
之前做分布式爬虫的时候,都是从push url来拿到爬虫消费的链接,这里提出一个问题,假如这个请求是post请求的呢,我观察了scrapy-redis的源码,其中spider.py的代码是这样写的 1.scrapy-redis源码分析 def make_request_from_data(self, data):"""Returns a Reques…...
Netty 性能优化与调试指南
Netty 是一款高性能的网络通信框架,其高性能得益于良好的设计和优化。但是在实际使用中,如果配置或实现不当,可能会导致性能下降或调试困难。本文将从性能优化和调试两方面入手,详细讲解如何在使用 Netty 时提高应用性能和诊断问题…...
网络安全产品之认识WEB应用防火墙
随着B/S架构的广泛应用,Web应用的功能越来越丰富,蕴含着越来越有价值的信息,应用程序漏洞被恶意利用的可能性越来越大,因此成为了黑客主要的攻击目标。传统防火墙无法解析HTTP应用层的细节,对规则的过滤过于死板&#…...
R学习——因子
目录 1 定义因子(factor函数) 2因子的作用 一个数据集中的 只需要考虑可以用哪个数据来进行分类就可以了,可以用来分类就可以作为因子。 Cy1这个因子对应的水平level是4 6 8: 1 定义因子(factor函数) 要…...
2024 亚马逊云科技re:Invent:Werner Vogels架构哲学,大道至简 六大经验助力架构优化
在2024亚马逊云科技re:Invent全球大会第四天的主题演讲中,亚马逊副总裁兼CTO Dr.Werner Vogels分享了 The Way of Simplexity,繁简之道,浓缩了Werner在亚马逊20年构建架构的经验。 Werner表示,复杂性总是会“悄无声息”地渗透进来…...
【代码随想录day58】【C++复健】 117. 软件构建(拓扑排序);47. 参加科学大会(dijkstra(朴素版)精讲)
117. 软件构建(拓扑排序) 继续边看解析边做题,思考时的问题做个如下的总结: 1. 存边用什么数据结构? 在题目中,我们需要存储节点之间的依赖关系(边信息)。选择适合的数据结构非常重…...
单目深度估计模型 lite-mono 测试
lite-mono 使用工业数据集kitti 进行训练,目的使用单目摄像头实现物体深度预测,关于kitti数据集的介绍和下载参考 (二)一文带你了解KITTI数据集-CSDN博客文章浏览阅读2.7w次,点赞64次,收藏294次。文章介绍…...
JAVA基础学习笔记_网络编程
文章目录 网络编程网络编程三要素IPIPv4细节InetAddress 端口号协议 UDPUDP协议(发数据)UDP协议(接受数据)UDP聊天室单播,组播,广播 TCP中文乱码问题代码细节,三次握手和四次挥手 网络编程 计算机之间通过网络进行数据传输 软件结构 C/S,Client/Server,客户端服务器,精美但麻…...
说下JVM中一次完整的GC流程?
大家好,我是锋哥。今天分享关于【说下JVM中一次完整的GC流程?】面试题。希望对大家有帮助; 说下JVM中一次完整的GC流程? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 在JVM中,垃圾回收(GC&am…...
鸿蒙NEXT开发案例:保质期计算
【引言】 保质期计算应用是一个基于鸿蒙NEXT框架开发的数字和文本统计组件。用户可以输入商品的生产日期和保质期天数,应用会自动计算并展示相关信息,包括保质状态、剩余天数、生产日期和到期日期。 【环境准备】 • 操作系统:Windows 10 …...
LLM并发加速部署方案(llama.cpp、vllm、lightLLM、fastLLM)
大模型并发加速部署 解析当前应用较广的几种并发加速部署方案! llama.cpp、vllm、lightllm、fastllm四种框架的对比: llama.cpp:基于C,①请求槽,②动态批处理,③CPU/GPU混合推理vllm:基于Pyth…...
用最小的代价解决mybatis-plus关于批量保存的性能问题
1.问题说明 问题背景说明,在使用达梦数据库时,mybatis-plus的serviceImpl.saveBatch()方法或者updateBatchById()方法的时候,随着数据量、属性字段的增加,效率越发明显的慢。 serviceImpl.saveBatch(); serviceImpl.updateBatch…...
蓝桥杯历届真题 --#递推 翻硬币(C++)
文章目录 思路完整代码结语 原题链接 思路 通过观察测试用例,我们猜测,从左到右依次对比每一个位置上的状态,如果不一样我们就翻一次,最终得到的答案即为正解。 完整代码 //这里是引入了一些常用的头文件,和一些常规操作 //第一…...