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 中,对销售数据按照销售额进行降序排序,是一项基础但极其重要的操作。 想象一下,您面前有…...

python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...

GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...