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

时间复杂度、空间复杂度实践练习(力扣OJ)

目录

文章目录

前言

题目一:轮转数组

 思路一:

 思路二:

思路三:

题目二:消失的数字

 思路一:

 思路二:

 思路三:

 题目三:移除元素

思路:

总结



 

前言

       想要编写高效的算法,了解时间复杂度是至关重要的。在本文中,我们将介绍一些时间复杂度和空间复杂度的练习,通过实际例子帮助您分析程序的时间复杂度和空间复杂度 ,前边已经了解过,复杂度是评价一个程序好坏标准,今天我们切身体验一下数据结构入门刷题。如何写出好的程序。


题目一:轮转数组

题目如下:

 题目给出的示例如下:

 思路一:

         没做过类似题目的人,大多数人思路或许是这样的:将数组最好一个元素保存,其他元素向后移动,再将保存的元素放在最前边。这也只是这道题的其中一种解题思路。但这个思路在力扣上过不去的。

        我们来分析一下这个思路:我们知道数组元素个数假设为n,但要将其他元素向后移动就需要进行n-1次,此外如果遇到最坏的情况我们需要轮转n-1次(执行n次就是原数组,n+1次就等价于轮转一次),每次执行n-1次,它的时间复杂度就是O(N^2),空间复杂度为O(1)。由此可见这个思路的效率很低,所以这个思路我就不再实现。

 思路二:

        我们观察一下初始数组和输出数组的特点,就可以很容易的想到这个思路:轮转几次就把后几个数字移到前边,把前边的部分移到后边。这个方法简单粗暴。

 代码实现:

void rotate(int* nums, int numsSize, int k)
{int *tmp = (int*)malloc( sizeof(int) * numsSize );k %= numsSize;memcpy(tmp,nums+numsSize-k,sizeof(int)*k);memcpy(tmp+k,nums,sizeof(int)*(numsSize-k));memcpy(nums,tmp,sizeof(int)*numsSize);free(tmp);
}

 它的时间复杂度为O(N),空间复杂度也为O(N)。用空间来换取效率,这个思路也并不是最优解。

思路三:

        我们也可以通过将数组元素逆置的方法来达到轮转的效果思路如下:

 代码实现:

void reverse(int* nums, int star, int end) {while (star < end) {int temp = nums[star];nums[star] = nums[end];nums[end] = temp;star++;end--;}
}void rotate(int* nums, int numsSize, int k) {k %= numsSize;reverse(nums, 0, numsSize - 1);reverse(nums, 0, k - 1);reverse(nums, k, numsSize - 1);
}

         这个思路的时间复杂度为O(N),空间复杂度为O(1)。这个思路才是这道题的最优解。

题目二:消失的数字

题目描述:

 思路一:

        题目中说到数组包含从0到n的所有整数,但缺少其中一个。那我们就可以先对数组的元素进行排序,然后遍历,如果下一个数据不等于下一个数加一,那么下一个数就是消失的数字。思路理清之后,我们可以先看一下这个思路的复杂度如何。

         复杂度也取决于排序的方法,最优的排序是使用qsort排序,时间复杂度为O(logN*N)。然后是遍历,根据大O的渐进表示法,估算出它的时间复杂度为O(logN*N)。可见这个方法的效率并不高,我们对于复杂度高的方法就不再实现。

 思路二:

         数组中的数据包含0到n所有整数,但缺失某一个,那我们就可以使用这个思路,将0到n看作一个等差数列,使用等差数列求和公式求和,最后将这个值依次减去数组中元素,最后的结果就是消失的数字。根据这个思路我们可以分析出它的时间复杂度是O(N)。

代码实现:

int missingNumber(int* nums, int numsSize){int n=numsSize;int ret=n*(n+1)/2;for(int i=0;i<n;i++){ret-=nums[i];}return ret;
}

 思路三:

        使用异或的方法,两个相同的数字异或的结果是0,并且异或符合乘法结合律,例如:1^2^1等于2,1^1^2也等于2。根据异或的这个特性,我们可以先异或0到n的所有数字,在将数组中所有元素依次异或,最终的结果就是消失的数字,根据思路我们可以估算出这个方法的时间复杂度也是O(N)。

代码实现:

int missingNumber(int* nums, int numsSize){
int ret=0;
for(int i=0;i<numsSize;i++)
{ret^=i;       ret^=nums[i];
}
return ret^numsSize;
}

 异或0到n的数字与数组同时异或就会少异或最后一个数字,所有最后返回时进行异或。

 

 题目三:移除元素

题目描述:

示例与说明:

 

         题目要求空间复杂度是O(1),并且数组还是无序的,返回的数组还要求是原来的顺序。看对于没做过类似题目的朋友,到这道题或许会感到头大,能想到的方法也大多数都很复杂。

        不要在意力扣的题目难度标签,力扣题目显示为简单的题目不一定简单,但难度标为中等或难的题目题解思路一定复杂。

思路:

        这里我向大家介绍一种很简单的方法,这种思路在其他很多场景中也是很常用的。我们可以遍历这个数组,如果数组中的元素与要删除的val值不相等就插入到数组中,如果相等就往后走。

 假设要删除2。

 

         0不等于2就插入数组,继续下一个,1与2不相等插入数组,继续向后遇到2不插入,原数组继续向后走。这个思路它的时间复杂度是O(N)。至于空间复杂度,题目要求空间复杂度为O(1),但这个方法显然空间复杂度是O(N),但是我们好好想一想,我们如果不选择创建新的数组,直接在原数组例插入,这样是否也可以。答案是可行的。依据这个思路我们将代码实现。

代码如下:

int removeElement(int* nums, int numsSize, int val) {int sz = numsSize;int pos=0;for (int i = 0; i < numsSize; i++){if (val != nums[i])nums[pos++]=nums[i];elsesz--;}return sz;
}

 方法简单快捷。


总结

        时间复杂度和空间复杂度有是衡量算法效率和算法好坏的重要指标,它直接关系到算法的执行速度和资源消耗。在本篇博客中,我们将通过了一系列时间复杂度和空间复杂度实战应用的练习,可以帮助您提升对算法效率的理解和应用能力,好的,到这里就要结束了,最后,感谢阅读!

相关文章:

时间复杂度、空间复杂度实践练习(力扣OJ)

目录 文章目录 前言 题目一&#xff1a;轮转数组 思路一&#xff1a; 思路二&#xff1a; 思路三&#xff1a; 题目二&#xff1a;消失的数字 思路一&#xff1a; 思路二&#xff1a; 思路三&#xff1a; 题目三&#xff1a;移除元素 思路&#xff1a; 总结 前言 想要编写高效的…...

JMeter(二十四)、使用吞吐量控制器实现不同的用户操纵不同的业务

一、需求 需求&#xff1a;博客系统&#xff0c;模拟用户真实行为&#xff0c;80%的用户阅读文章&#xff0c;20%的用户创建文章&#xff0c;创建文章的用户随机的删除或者修改文章。 二、脚本实现 80%的用户查看文章 20%用户创建文章 根据post_id是否能整除2&#xff0c;决…...

8.1Jmeter5.1:Jmeter SSL

Jmeter配置证书请求双向认证SSL的web接口 需求:需要通过Jmeter配置证书请求双向认证SSL的web接口 提供的证书:P12格式 备注:Jmeter需要导入的证书是keystore证书 那么要先把P12转成keystore文件 1、使用p12生成keystore文件 keytool介绍 这里需要提到提到jdk自带的key…...

7-7 找最小的字符串 (15 分)

7-7 找最小的字符串 &#xff08;15 分) 本题要求编写程序&#xff0c;针对输入的N个字符串&#xff0c;输出其中最小的字符串。 输入格式&#xff1a; 输入第一行给出正整数N&#xff1b;随后N行&#xff0c;每行给出一个长度小于80的非空字符串&#xff0c;其中不会出现换行…...

Red Hat 安装MySQL 8.0与 Navicat

目录 Red Hat 安装 MySQL 8.0 1、更新软件包列表 2、安装MySQL服务器和客户端 3、启动MySQL服务 4、确保MySQL服务器正在运行 5、root 用户的密码 6、登录MySQL&#xff0c;输入mysql密码 7、MySQL默认位置 Red Hat 安装 Navicat 1、下载 Navicat 2、执行命令 Red H…...

17游刃有余:动手实现自己的RPC框架(三)

这篇文章我们来实现跨语言的网络通信。 跨语言RPC框架的必要性主要体现在以下几个方面: 解决不同语言之间的互操作性。不同语言使用的数据类型和序列化方式可能不同,跨语言 RPC 框架可以提供通用的编解码库和语言适配器,以便将不同语言的数据转换为通用的格式进行通信。实现…...

c语言——求n之内的素数和

//求n之内的素数和 //列如&#xff1a;2、3、5等 #include<stdio.h> #include<math.h> int main() {int i,j,k,n0;scanf("%d",&n);for(i2;i<n;i){k(int)sqrt(i);for(j2;j<k;j)if(i%j0)break;if(j>k){printf("%d,",i);n;if(n%50)p…...

【M波段2D双树(希尔伯特)小波多分量图像去噪】基于定向M波段双树(希尔伯特)小波对多分量/彩色图像进行降噪研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

unity TextMeshPro 富文本

<b>粗体标签</b> <i>斜体标签</i> <u>下划线标签</u> <s>删除线标签</s> <sup>上标标签</sup>前面后边上标签 5<sup>。</sup>C <sub>下标标签&#xff0c;如&#xff1a;</sub>H<sub&…...

【PyTorch】PyTorch、Cuda 的安装和使用

原文作者&#xff1a;我辈李想 版权声明&#xff1a;文章原创&#xff0c;转载时请务必加上原文超链接、作者信息和本声明。 文章目录 前言一、Anaconda 中安装 PyTorch 和 CUDA二、检查PyTorch和CUDA版本三、PyTorch的基本使用四、PyTorch调用cuda五、Matplotlib绘制Pytorch损…...

1.初识typescript

在很多地方的示例代码中使用的都是ts而不是js&#xff0c;为了使用那些示例&#xff0c;学习ts还是有必要的 JS有的TS都有&#xff0c;JS与TS的关系很像css与less ts在运行前需要先编译为js&#xff0c;浏览器不能直接运行ts 目录 1 编译TS的工具包 1.1 安装 1.2 基本…...

iPhone 6透明屏是什么?原理、特点、优势

iPhone 6透明屏是一种特殊的屏幕技术&#xff0c;它能够使手机屏幕变得透明&#xff0c;让用户能够透过屏幕看到手机背后的物体。 这种技术在科幻电影中经常出现&#xff0c;给人一种未来科技的感觉。下面将介绍iPhone 6透明屏的原理、特点以及可能的应用。 iPhone 6透明屏的原…...

prometheus+grafana进行服务器资源监控

在性能测试中&#xff0c;服务器资源是值得关注一项内容&#xff0c;目前&#xff0c;市面上已经有很多的服务器资 源监控方法和各种不同的监控工具&#xff0c;方便在各个项目中使用。 但是&#xff0c;在性能测试中&#xff0c;究竟哪些指标值得被关注呢&#xff1f; 监控有…...

EventBus 开源库学习(三)

源码细节阅读 上一节根据EventBus的使用流程把实现源码大体梳理了一遍&#xff0c;因为精力有限&#xff0c;所以看源码都是根据实现过程把基本流程看下&#xff0c;中间实现细节先忽略&#xff0c;否则越看越深不容易把握大体思路&#xff0c;这节把一些细节的部分再看看。 …...

zjzcyList.stream().map(Pb_zjzcy::getZjid).collect(Collectors.toList()); 解释一下

zjzcyList.stream().map(Pb_zjzcy::getZjid).collect(Collectors.toList()); 解释一下 这段代码是使用Java 8的流式处理&#xff08;Stream&#xff09;对一个存储了对象的列表&#xff08;zjzcyList&#xff09;进行操作&#xff0c;并最终返回一个包含了列表中每个对象的Zji…...

车载总线系列——J1939 二

车载总线系列——J1939 二 我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 没有人关注你。也无需有人关注你。你必须承认自己的价值&#xff0c;你不能站…...

【C#学习笔记】引用类型(2)

文章目录 ObjectEqualsGetTypeToStringGetHashCode string逐字文本复合格式字符串字符串内插 StringBuilderStringBuilder 的工作原理StringBuilder提供的方法访问字符迭代字符查询字符 dynamic Object 支持 .NET 类层次结构中的所有类&#xff0c;并为派生类提供低级别服务。…...

【Rust 基础篇】Rust类函数宏:代码生成的魔法

导言 Rust是一门现代的、安全的系统级编程语言&#xff0c;它提供了丰富的元编程特性&#xff0c;其中类函数宏&#xff08;Function-Like Macros&#xff09;是其中之一。类函数宏允许开发者创建类似函数调用的宏&#xff0c;并在编译期间对代码进行生成和转换。在本篇博客中…...

Spring-1-透彻理解Spring XML的Bean创建--IOC

学习目标 上一篇文章我们介绍了什么是Spring,以及Spring的一些核心概念&#xff0c;并且快速快发一个Spring项目&#xff0c;实现IOC和DI&#xff0c;今天具体来讲解IOC 能够说出IOC的基础配置和Bean作用域 了解Bean的生命周期 能够说出Bean的实例化方式 一、Bean的基础配置 …...

【JAVA】类和对象

作者主页&#xff1a;paper jie的博客 本文作者&#xff1a;大家好&#xff0c;我是paper jie&#xff0c;感谢你阅读本文&#xff0c;欢迎一建三连哦。 本文录入于《JAVASE语法系列》专栏&#xff0c;本专栏是针对于大学生&#xff0c;编程小白精心打造的。笔者用重金(时间和精…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

Cursor AI 账号纯净度维护与高效注册指南

Cursor AI 账号纯净度维护与高效注册指南&#xff1a;解决限制问题的实战方案 风车无限免费邮箱系统网页端使用说明|快速获取邮箱|cursor|windsurf|augment 问题背景 在成功解决 Cursor 环境配置问题后&#xff0c;许多开发者仍面临账号纯净度不足导致的限制问题。无论使用 16…...