力扣刷题第1天:消失的数字

      大家好啊,从今天开始将会和大家一起刷题,从今天开始小生也会开辟新的专栏。😜😜😜

目录

第一部分:题目描述

第二部分:题目分析

第三部分:解决方法

3.1 思路一:先排序再查找

3.2 思路二:公式运算

3.3 思路三:异或运算

第四部分:代码实现

第五部分:总结收获


第一部分:题目描述

第二部分:题目分析

    由图片分析可得,该题目对算法时间复杂度有一定的要求时间复杂度为O(N),这是关键所在,也就是说只能遍历一遍数组,便可以找到缺失的那个数字。

第三部分:解决方法

3.1 思路一:先排序再查找

     既然是0~n内的整数,且仅仅缺少了一个整数,那么我们就可以先对该数组进行排序,再检验相邻下标的元素是否相差为1,理论上便可以得出最后的结果。但是不得不提醒大家,排序的复杂度是相当高的,即便是最复杂度最小的快排,在这个程序内也不合适。我们可以通过图片来认识。

      由该表可知,当我们使用效率最高的排序且考虑最坏的情况时,复杂度为N*log(N),显然在这个题目中超出了复杂度的要求,因此,这种思路虽然是最直接的但是一定会超时。别慌,我们再想想其他办法。

3.2 思路二:公式运算

      具体问题具体分析,0-n它是一个等差数列,既然我们该数组存储的是0~n里面的整数且只缺少了一个整数,那我们可以用将0 ~ n所有的整数相加,再把该数组中的整数元素相加,最后把这两个相加后的结果相减,便会得到消失的那个数字,直接返回即可。

       但是我们可以举一反三,如果题目更改一下,缺失的并非一个数字而是多个数字呢?那这种方法是不是就不起作用啦?这种方法还是不错的,那有没有更加普适性的方法呢?大家可以思考一下。

3.3 思路三:异或运算

       异或运算是属于位运算的一种,它是按照位置进行运算的,位与位异或,相同为0,不相同为1,同时,位运算(按位与、按位或、按位异或)是满足交换律和结合律的,因此,位运算它是没有顺序之分的,改变数的运算顺序,并不会改变最后的结果。

        在这道题中,解题的思路在于:两个相同的数异或结果一定是0,0和任何数异或是它本身,因此,我们只需要定义一个初始化为0的变量,依次与该数组每个数字异或,然后和0~n的每一个数字再进行异或,最后留下来的便是所求的数字了。(双爆胎数字异或结果为0,再与其他数异或,并不会改变这个数,最后只剩下单独出现的那个数字,也就是缺失的数字。)

第四部分:代码实现

方法一代码详解:定义两个变量,一个通过循环存储0~n所有数字的和,一个通过循环存储数组所有元素的和,最后相减即可。

     注意这里的numSize是数组中的整数的最大取值也就是n, 同时也是数组中的元素个数(数组长度),是通过参数传递的方式进来的。

时间复杂度:O(n)
空间复杂度:O(1)

int Missingnum(int* nums, int numsSize)
{int sum1 = 0;int sum2 = 0;//1.求出0~n所有元素之和for (int i = 0; i < numsSize + 1; i++){sum1 =sum1+ i;}//2.求出数组所有元素之和for (int j = 0; j < numsSize; j++){sum2 =sum2+ nums[j];}//3.直接返回相减的结果return sum1 - sum2;
}

方法二代码详解:定义一个初始化为0的变量,依次与该数组(n个元素)和0~n(n+1个元素)的每一个数字异或,最后留下来的便是所求的数字了。

时间复杂度:O(n)
空间复杂度:O(1)

int Missingnum(int* nums, int numsSize)
{int tmp = 0;//1.依次与数组的每一个元素异或for (int i = 0; i < numsSize; i++){tmp = tmp ^ nums[i];}//2.依次与0~n数字异或for (int j = 0; j < numsSize +1; j++){tmp = tmp ^j;}//3.返回异或的结果return tmp;
}

第五部分:总结收获

        通过这道题,  深刻体会到位运算中异或的巧妙之处,主要是利用了异或的重要性质:两个相同的数异或结果一定是0,0和任何数异或是它本身,并且满足交换律和结合律的,因此,位运算它是没有顺序之分的,改变数的运算顺序,并不会改变最后的结果。

      在后面的刷题中,注意总结这类题型,达到触类旁通!

         在后续更新中,我会一直写关于OJ题的题解,有兴趣的小伙伴可以关注作者,和作者讨论其他OJ题目,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!制作不易,如有不正之处敬请指出,感谢大家的来访,UU们的观看是我坚持下去的动力,
在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/323394.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

企业短信平台群发_专业群发短信平台

企业平台群发是一种方便、高效的营销方式&#xff0c;通过专业群发平台&#xff0c;企业能够快速、准确地向大量目标客户发送&#xff0c;提高品牌知名度、促进销售和客户互动。下面将详细介绍企业短信平台群发的优势及使用方法。 优势 提高信息覆盖率 企业平台群发可以让企业…

html--瀑布效果

<!doctype html> <html> <head> <meta charset"utf-8"> <title>瀑布效果</title><style> body {background: #222;color: white;overflow:hidden; }#container {box-shadow: inset 0 1px 0 #444, 0 -1px 0 #000;height: 1…

Vue 插槽

Vue插槽是一种特殊的语法&#xff0c;用于在组件中定义可复用的模板部分。它允许开发者在组件的标记中声明一个或多个插槽&#xff0c;然后在使用该组件时&#xff0c;可以根据自己的需求将内容插入到这些插槽中。 Vue插槽分为默认插槽和具名插槽两种。 目录 默认插槽 语法…

【图书推荐】《JSP+Servlet+Tomcat应用开发从零开始学(第3版)》

本书目的 系统讲解JSPServletTomcat开发技术&#xff0c;帮助读者用最短的时间掌握Java Web应用开发技能。 内容简介 本书全面系统地介绍JSPServletTomcat开发中涉及的相关技术要点和实战技巧。本书内容讲解循序渐进&#xff0c;结合丰富的示例使零基础的读者能够熟练掌握JSP…

Leetcode—2105. 给植物浇水 II【中等】

2024每日刷题&#xff08;131&#xff09; Leetcode—2105. 给植物浇水 II 实现代码 class Solution { public:int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {int size plants.size();int i 0;int j size - 1;int capA capacityA;in…

探秘Tailwind CSS:前端开发的加速器(Tailwind CSS让CSS编写更简洁)

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 Tailwind CSS 📒📝 快速体验📝 深入学习⚓️ 相关链接 ⚓️📖 介绍 📖 在这个快速迭代的互联网时代,前端开发效率和设计质量的双重要求,使得开发者们不断寻求更高效的工具和方法。今天,我们要介绍的是一个能够极大…

酷柚易汛ERP源码部署/售后更新/搭建/上线维护

一款基于FastAdminThinkPHPLayui开发的ERP管理系统&#xff0c;帮助中小企业实现ERP管理规范化&#xff0c;此系统能为你解决五大方面的经营问题&#xff1a;1.采购管理 2.销售管理 3.仓库管理 4.资金管理 5.生产管理&#xff0c;适用于&#xff1a;服装鞋帽、化妆品、机械机电…

设计模式之服务定位器模式

想象一下&#xff0c;你的Java应用是一座庞大的迷宫&#xff0c;里面藏着无数宝贵的服务宝藏&#xff0c;而你正需要一张精确的藏宝图来指引方向&#xff0c;迅速找到并利用这些宝藏。服务定位器模式&#xff0c;正是这样一张神奇的地图&#xff0c;它帮你动态定位并获取应用中…

『先进技术助力』Kompas AI:智能AI代理在工作中的应用与效率提升

『智能化未来』Kompas AI如何改变我们的工作方式&#xff1f; 在这个信息时代&#xff0c;利用AI聊天机器人来处理机械性的工作已经成为一种趋势。ChatGPT作为一种智能助手&#xff0c;不仅能够提高工作效率&#xff0c;还可以帮助我们更明智地做出决策&#xff0c;从而释放出更…

内网安全综合管理系统是什么 | 好用的内网安全管理系统有哪些

内网安全综合管理系统是指一种集成终端管理、网络管理、内容管理、资产管理等功能的综合性安全管理系统。它主要对内网上的主机进行统一安全管理&#xff0c;包括对网络主机用户操作实施监督控制&#xff0c;并对主机中的安全软件&#xff08;如主机入侵监测系统、主机防火墙和…

C++:内存管理

C:内存管理 一、C/C内存分布二、C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free三、C内存管理方式1.new/delete操作内置类型2.new和delete操作自定义类型 四、operator new与operator delete函数&#xff08;重点&#xff09;五、new和delete的实现原理1.内置…

【算法】滑动窗口——水果成篮

本篇博客是我对“水果成篮”这道题由暴力解法到滑动窗口思路的具体思路&#xff0c;有需要借鉴即可。 目录 1.题目2.暴力求解3.暴力优化3.1每次right不用回退3.2有些left长度一定不如前一个&#xff0c;不用走&#xff0c;left不回退 4.滑动窗口算法5.总结 1.题目 题目链接&am…

工程技术综合SCI期刊,中科院2区,IF=3+,对国人非常友好!

一、期刊名称 Engineering Analysis with Boundary Elements 二、期刊简介概况 期刊类型&#xff1a;SCI 学科领域&#xff1a;工程技术 影响因子&#xff1a;3.3 中科院分区&#xff1a;2区 出版方式&#xff1a;订阅模式/开放出版 版面费&#xff1a;选择开放出版需支…

MySQL——利用变量进行查询操作

新建链接&#xff0c;自带world数据库&#xff0c;里面自带city表格。 DQL # MySQL利用变量进行查询操作 set cityNameHaarlemmermeer; select * from city where NamecityName;# 多个结果查询 set cityName1Haarlemmermeer; set cityName2Breda; set cityName3Willemstad; s…

何为基差?股指期货的升水和贴水又怎么理解?

基差是一个金融术语&#xff0c;它指的是现货价格和期货价格之间的差额。在股指期货市场中&#xff0c;现货就是指实际的股票指数&#xff0c;而期货则是基于这个指数未来某个时间点的价格预期。基差可以是正的或负的&#xff0c;具体取决于期货价格是高于还是低于现货价格。 1…

Dbeaver连接一段时间不操作后断开的问题

右键数据库连接点击编辑连接点击初始化将连接保持改成60s

大势所趋!企业网站HTTPS升级全面普及化

JoySSL官网 注册码230918 HTTPS加密协议的应用无疑是维护网络信息安全的重要一环。随着技术的不断进步与用户隐私意识的增强&#xff0c;HTTPS加密已不再仅仅是大型企业的专属&#xff0c;而是逐渐成为所有企业网站的标准配置&#xff0c;其普及化趋势显而易见&#xff0c;堪称…

【JavaEE网络】HTTP/HTTPS协议的工作原理与格式详解

目录 HTTP/HTTPSHTTP是什么理解“应用层协议”理解HTTP协议的工作过程HTTP协议格式 HTTP/HTTPS HTTP是什么 应用层&#xff0c;一方面是需要自定义协议&#xff0c;一方面也会用到一些现成的协议 HTTP及HTTPS是应用层重点协议 使用浏览器&#xff0c;打开网站&#xff0c;这…

AI大模型探索之路-训练篇18:大语言模型预训练-微调技术之Prompt Tuning

系列篇章&#x1f4a5; AI大模型探索之路-训练篇1&#xff1a;大语言模型微调基础认知 AI大模型探索之路-训练篇2&#xff1a;大语言模型预训练基础认知 AI大模型探索之路-训练篇3&#xff1a;大语言模型全景解读 AI大模型探索之路-训练篇4&#xff1a;大语言模型训练数据集概…

ChatGPT开源的whisper音频生成字幕

1、前言 好了&#xff0c;那接下来看一下whisper开源库的介绍 有五种模型大小&#xff0c;其中四种仅支持英语&#xff0c;提供速度和准确性的权衡。上面便是可用模型的名称、大致的内存需求和相对速度。如果是英文版的语音&#xff0c;直接想转换为英文。 本来我是想直接在我的…