当前位置: 首页 > news >正文

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标题均已插入超链接&#xff0c;点击可直接跳转~ 一、消失的数字 1、题目描述 数组nums包含从0到n的所有整数&#xff0c;但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗&#xff1f; 2、题目分析 &#xff08;1&#xff09;numsS…...

【CentOS 】DHCP 更改为静态 IP 地址并且遇到无法联网

文章目录 引言解决方式标题1. **编辑网络配置文件**&#xff1a;标题2. **确保配置文件包含以下内容**&#xff1a;特别注意 标题3. **重启网络服务**&#xff1a;标题4. **检查配置是否生效**&#xff1a;标题5. **测试网络连接**&#xff1a;标题6. **检查路由表**&#xff1…...

Linux 操作系统 --- 信号

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

黑马前端——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爬虫】技术深度探索与实践

目录 引言 第一部分&#xff1a;Python爬虫基础 1.1 网络基础 1.2 Python爬虫基本流程 第二部分&#xff1a;进阶技术 2.1 动态网页抓取 2.2 异步编程与并发 2.3 反爬虫机制与应对 第三部分&#xff1a;实践案例 第四部分&#xff1a;法律与道德考量 第五部分&#x…...

智启万象|挖掘广告变现潜力,保障支付安全便捷

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

函数递归,匿名、内置行数,模块和包,开发规范

一、递归与二分法 一&#xff09;递归 1、递归调用的定义 递归调用&#xff1a;在调用一个函数的过程中&#xff0c;直接或间接地调用了函数本身 2、递归分为两类&#xff1a;直接与间接 #直接 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

使用命令提示符&#xff08;CMD&#xff09;进行扫描 查看本机IP地址 首先通过 ipconfig /all 命令查看本机的IP地址&#xff0c;确定你的网段&#xff0c;例如 192.168.1.。 Ping网段内每个IP地址 接着使用循环命令&#xff1a; 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 连续变量&#xff08;1&#xff09;集中趋势&#xff08;2&#xff09;离散趋势&#xff08;3&#xff09;分布特征 3.2 分类变量&#xff08;1&#xff09;单个分类变量&#xff08;2&#xff09;多个分类变量 3.1 连续变量 &#xff08;1&#xff09;集中趋势 …...

2024年杭州市网络与信息安全管理员(网络安全管理员)职业技能竞赛的通知

2024年杭州市网络与信息安全管理员&#xff08;网络安全管理员&#xff09;职业技能竞赛的通知 一、组织机构 本次竞赛由杭州市总工会牵头&#xff0c;杭州市人力资源和社会保障局联合主办&#xff0c;杭州市萧山区总工会承办&#xff0c;浙江省北大信息技术高等研究院协办。…...

SpringBoot参数校验详解

前言 在web开发时&#xff0c;对于请求参数&#xff0c;一般上都需要进行参数合法性校验的&#xff0c;原先的写法时一个个字段一个个去判断&#xff0c;这种方式太不通用了&#xff0c;Hibernate Validator 是 Bean Validation 规范的参考实现&#xff0c;用于在 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 &#xff0c;请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数&#xff0c;应与元素在两个数组中都出现的次数一致&#xff08;如果出现次数不一致&#xff0c;则考虑取较小值&#xff09;。可…...

基于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-笔记

上传图片木马文件后看到&#xff0c;检查的文件内容&#xff0c;包含<? 一句话木马提示 检查的文件格式 用如下图片木马&#xff0c;加上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 篇(二) - 卫星导航定位原理

专栏文章目录传送门&#xff1a;返回专栏目录 Hi, 我是你们的老朋友&#xff0c;主要专注于嵌入式软件开发&#xff0c;有兴趣不要忘记点击关注【码思途远】 文章目录 关注星号公众号&#xff0c;不容错过精彩 作者&#xff1a;HywelStar Hi, 我是你们的老朋友HywelStar, 根…...

怎样在 SQL 中对一个包含销售数据的表按照销售额进行降序排序?

在当今数字化商业的浪潮中&#xff0c;数据就是企业的宝贵资产。对于销售数据的有效管理和分析&#xff0c;能够为企业的决策提供关键的支持。而在 SQL 中&#xff0c;对销售数据按照销售额进行降序排序&#xff0c;是一项基础但极其重要的操作。 想象一下&#xff0c;您面前有…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

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

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...