2.2算法的时间复杂度与空间复杂度——经典OJ
本博客的OJ标题均已插入超链接,点击可直接跳转~
一、消失的数字
1、题目描述
数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?
2、题目分析
(1)numsSize表示的是数组中元素的个数
(2)思路一
暴力旋转——将最后一个数用tmp存起来,剩下的数依次往后挪,再把tmp放到数组首位,循环往复直至满足题意
这里需要理清这个算法的时间复杂度,解析如图(设numsSize=N)
从示例1不难看出,真实旋转次数是k%numsSize,也就是k%N,从周期的角度就可以理解这一点;每转一次就要把整个数组动一遍,那转k次就要动k*N遍,时间复杂度就出来了,显然不符合题目要求
(3)思路二
三步逆置法
- 第一步:前N-k个逆置=>4 3 2 1 5 6 7
- 第二步:后k个逆置=>4 3 2 1 7 6 5
- 第三步:整体逆置=>5 6 7 1 2 3 4
分析本算法的时间复杂度:可以看出遍历了3次数组,复杂度为O(N),满足题目要求
具体代码实现如下
//三步逆置法
void reverse(int*nums,int left,int right)
{while(left <= right){int tmp=nums[left];nums[left]=nums[right];nums[right]=tmp;left++;right--;}}
void rotate(int* nums, int numsSize, int k)
{k=k%numsSize;//算出真正的轮转次数reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);
}
二、 旋转数组/轮转数组
1、题目描述
给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。
2、题目分析
思路1由于排序的时间复杂度较高,先舍弃掉
(1)思路二
先把0-N所有数加起来,然后依次减去原数组中的值
int missingNumber(int* nums, int numsSize)
{int N=numsSize;int ret=N(N+1)/2//此处计算参考等差数列求和公式for(int i=0;i<numsSize;i++){ret=ret-nums[i];}return ret;
}
(2)思路三
用异或解决,此处异或满足“交换律”,读者可自行验证
举例来说:1 ^ 2 ^ 1=2,1 ^ 1 ^ 2=2
具体代码实现如下
int missingNumber(int* nums, int numsSize)
{int x=0;for(int i=0;i<numsSize;i++){x=x^nums[i];}for(int i=0;i<=numsSize;i++){x=x^i;}return x;
}
相关文章:

2.2算法的时间复杂度与空间复杂度——经典OJ
本博客的OJ标题均已插入超链接,点击可直接跳转~ 一、消失的数字 1、题目描述 数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗? 2、题目分析 (1)numsS…...

【CentOS 】DHCP 更改为静态 IP 地址并且遇到无法联网
文章目录 引言解决方式标题1. **编辑网络配置文件**:标题2. **确保配置文件包含以下内容**:特别注意 标题3. **重启网络服务**:标题4. **检查配置是否生效**:标题5. **测试网络连接**:标题6. **检查路由表**࿱…...

Linux 操作系统 --- 信号
序言 在本篇内容中,将为大家介绍在操作系统中的一个重要的机制 — 信号。大家可能感到疑惑,好像我在使用 Linux 的过程中并没有接触过信号,这是啥呀?其实我们经常遇到过,当我们运行的进程当进程尝试访问非法内存地址时…...

黑马前端——days09_css
案例 1 页面框架文件 <!DOCTYPE html> <html lang"zh-CN"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><meta http-equiv"X-UA-Compati…...
【Python爬虫】技术深度探索与实践
目录 引言 第一部分:Python爬虫基础 1.1 网络基础 1.2 Python爬虫基本流程 第二部分:进阶技术 2.1 动态网页抓取 2.2 异步编程与并发 2.3 反爬虫机制与应对 第三部分:实践案例 第四部分:法律与道德考量 第五部分&#x…...

智启万象|挖掘广告变现潜力,保障支付安全便捷
谷歌致力于为开发者提供 先进的广告变现与支付解决方案 一起回顾 2024 Google 开发者大会 了解如何利用谷歌最新工具和功能 提高变现收入,优化用户体验,保障交易安全 让变现更上一层楼 广告检查器是谷歌 AdMob 平台最新推出的高级测试工具,开…...

函数递归,匿名、内置行数,模块和包,开发规范
一、递归与二分法 一)递归 1、递归调用的定义 递归调用:在调用一个函数的过程中,直接或间接地调用了函数本身 2、递归分为两类:直接与间接 #直接 def func():print(from func)func()func() # 间接 def foo():print(from foo)bar…...

Springboot3 整合swagger
一、pom.xml <dependency><groupId>org.springdoc</groupId><artifactId>springdoc-openapi-starter-webmvc-api</artifactId><version>2.1.0</version></dependency> 二、application.yml # SpringDoc配置 # springdoc:swa…...
查看同一网段内所有设备的ip
使用命令提示符(CMD)进行扫描 查看本机IP地址 首先通过 ipconfig /all 命令查看本机的IP地址,确定你的网段,例如 192.168.1.。 Ping网段内每个IP地址 接着使用循环命令: for /L %i IN (1,1,254) DO ping -w 1 -n …...

Spark MLlib 特征工程(上)
文章目录 Spark MLlib 特征工程(上)特征工程预处理 Encoding:StringIndexer特征构建:VectorAssembler特征选择:ChiSqSelector归一化:MinMaxScaler模型训练总结Spark MLlib 特征工程(上) 前面我们一起构建了一个简单的线性回归模型,来预测美国爱荷华州的房价。从模型效果来…...

《SPSS零基础入门教程》学习笔记——03.变量的统计描述
文章目录 3.1 连续变量(1)集中趋势(2)离散趋势(3)分布特征 3.2 分类变量(1)单个分类变量(2)多个分类变量 3.1 连续变量 (1)集中趋势 …...
2024年杭州市网络与信息安全管理员(网络安全管理员)职业技能竞赛的通知
2024年杭州市网络与信息安全管理员(网络安全管理员)职业技能竞赛的通知 一、组织机构 本次竞赛由杭州市总工会牵头,杭州市人力资源和社会保障局联合主办,杭州市萧山区总工会承办,浙江省北大信息技术高等研究院协办。…...
SpringBoot参数校验详解
前言 在web开发时,对于请求参数,一般上都需要进行参数合法性校验的,原先的写法时一个个字段一个个去判断,这种方式太不通用了,Hibernate Validator 是 Bean Validation 规范的参考实现,用于在 Java 应用中…...
安全基础学习-SHA-1(Secure Hash Algorithm 1)算法
SHA-1(Secure Hash Algorithm 1)是一种密码学哈希函数,用于将任意长度的输入数据(消息)转换成一个固定长度的输出(哈希值或摘要),长度为160位(20字节)。SHA-1的主要用途包括数据完整性验证、数字签名、密码存储等。 1、SHA-1 的特性 定长输出:无论输入数据长度是多…...

leetcode350. 两个数组的交集 II,哈希表
leetcode350. 两个数组的交集 II 给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可…...

基于YOLOv8的缺陷检测任务模型训练
文章目录 一、引言二、环境说明三、缺陷检测任务模型训练详解3.1 PCB数据集3.1.1 数据集简介3.1.2 数据集下载3.1.3 构建yolo格式的数据集 3.2 基于ultralytics训练YOLOv83.2.1 安装依赖包3.2.2 ultralytics的训练规范说明3.2.3 创建训练配置文件3.2.4 下载预训练模型3.2.5 训练…...

【upload]-ini-[SUCTF 2019]CheckIn-笔记
上传图片木马文件后看到,检查的文件内容,包含<? 一句话木马提示 检查的文件格式 用如下图片木马,加上GIF89a绕过图片和<?检查 GIF89a <script languagephp>eval($_POST[cmd])</script> .user.ini实际上就是一个可以由用…...
uniapp条件编译使用教学(#ifdef、#ifndef)
#ifdef //仅在xxx平台使用#ifndef //除了在xxx平台使用#endif // 结束 标识平台APP-PLUSAPPMP微信小程序/支付宝小程序/百度小程序/头条小程序/QQ小程序MP-WEIXIN微信小程序MP-ALIPAY支付宝小程序MP-BAIDU百度小程序MP-TOUTIAO头条小程序MP-QQQQ小程序H5H5APP-PLUS-NVUEApp nv…...

NXP i.MX8系列平台开发讲解 - 4.1.2 GNSS 篇(二) - 卫星导航定位原理
专栏文章目录传送门:返回专栏目录 Hi, 我是你们的老朋友,主要专注于嵌入式软件开发,有兴趣不要忘记点击关注【码思途远】 文章目录 关注星号公众号,不容错过精彩 作者:HywelStar Hi, 我是你们的老朋友HywelStar, 根…...
怎样在 SQL 中对一个包含销售数据的表按照销售额进行降序排序?
在当今数字化商业的浪潮中,数据就是企业的宝贵资产。对于销售数据的有效管理和分析,能够为企业的决策提供关键的支持。而在 SQL 中,对销售数据按照销售额进行降序排序,是一项基础但极其重要的操作。 想象一下,您面前有…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...