当前位置: 首页 > 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;您面前有…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

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

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

使用 SymPy 进行向量和矩阵的高级操作

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

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

GruntJS-前端自动化任务运行器从入门到实战

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