力扣刷题第0天:只出现一次的数字

devtools/2024/9/24 18:34:45/

目录

第一部分:题目描述

​第二部分:题目分析

第三部分:解决方法

3.1思路1:    双指针暴力求解

         3.2 思路2:异或运算

第四部分:总结收获


第一部分:题目描述


第二部分:题目分析

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

第三部分:解决方法

3.1思路1:双指针暴力求解

       定义两个整型变量代表指针,利用双层for循环,外层循环i指向每个元素,内层循环j开始从当前元素的下个位置开始遍历整个数组,寻找是否存在与该元素相同的元素。如果发现了一个相同的元素,计数器加1,否则内层循环继续往下遍历,内层循环结束了但是没有发现相同的元素,那么count一直为0,并且i下标对应的元素a[i]就是单独出现的元素,直接返回即可,当内层循环处理一遍之后,继续处理外层循环的下一个元素i+1,直到把每一个元素都查找过。    但是时间复杂度为:O(n^2)不符合要求。


int singleNumber(int* nums, int len) 
{	int i = 0;//1.针对外层循环每个元素,让内层循环依次与之进行对比for (; i < len; i++){int count = 0;//2.内层循环从下一个位置开始,进行比对,同时记录,出现相同的次数for (int j = i+1; j < len; j++){if (nums[i] == nums[j]){count++;	//每出现相同的元素,计数器就会加1}}//3.说明没有找到相同的元素,直接返回下标i对应的元素即可if (count == 0){return nums[i];}	}return -1;  
}

3.2 思路2:异或运算

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

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

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

第四部分:总结收获

      在数组的遍历中,可以利用整型变量/下标来代替指针,用于标记元素的位置,这道题引入了双指针思想来通过双层for循环暴力求解问题,这是算法题中一个基本的思想,必须熟练掌握。此外,异或运算具有“消消乐”的特点,需要注意。

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


http://www.ppmy.cn/devtools/33841.html

相关文章

JavaScript面试题(浏览器)

1.浏览器兼容性问题 不同浏览器的内核不尽相同&#xff0c;所以各个浏览器对网页的解析存在一定的差异。浏览器内核主要分为两种&#xff0c;一是渲染引擎&#xff0c;另一个是js 引擎。所以浏览器兼容性问题一般指&#xff1a;css兼容、js兼容。 CSS兼容&#xff1a; (1). 不…

springboot模块以及非springboot模块构成的多模块maven项目最佳构建方式

文章目录 背景一般的实现使用spring-boot-dependencies 更优雅的实现. 背景 有时候构建一个多模块maven项目其中某一个模块是web-service需要使用spring boot,其他模块跟spring boot 完全无关,本文总结一下在这个场景下maven项目最佳构建方式. 一般的实现 网上应该也看到过很…

STM32中断之TIM定时器详解

系列文章目录 STM32单片机系列专栏 C语言术语和结构总结专栏 文章目录 1. TIM简述 2. 定时器类型 2.1 基本定时器 2.2 通用定时器 2.3 高级定时器 3. 定时中断 4. 代码示例1 5. 代码示例2 1. TIM简述 定时器的基本功能&#xff1a;定时器可以在预定的时间间隔内产生周…

设计模式-03 设计模式-工厂模式factory-内部工厂

设计模式-03 设计模式-工厂模式factory-内部工厂 目录 设计模式-03 设计模式-工厂模式factory-内部工厂 1.定义 2.内涵 3.案例对比 4.特点 4.总结 1.定义 内部工厂模式是一种创建类对象的方式&#xff0c;其中工厂方法被封装在类内部&#xff0c;客户端只能通过类的公共…

消费品行业的5G新时代:2024年消费品行业趋势洞察报告

来源&#xff1a;安永 2023 年&#xff0c;我国社会消费品零售总额达人民币 47.147.147.147.1万亿元&#xff0c;比上年增长 7.2%7.2%7.2%7.2%&#xff1b;最终 消费支出拉动经济增长 4.34.34.3个百分点&#xff0c;比上年提高 3.13.13.1个百分点&#xff0c;对经济增长的贡献…

分类预测 | Matlab实现POA-BP鹈鹕算法优化BP神经网络多特征分类预测

分类预测 | Matlab实现POA-BP鹈鹕算法优化BP神经网络多特征分类预测 目录 分类预测 | Matlab实现POA-BP鹈鹕算法优化BP神经网络多特征分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 1.Matlab实现POA-BP鹈鹕算法优化BP神经网络多特征分类预测&#xff08;Matlab实…

大模型T5

近年来&#xff0c;在大规模预训练语言模型上&#xff0c;各大公司的军备竞赛卷得十分激烈&#xff01; 本文我们介绍Google推出的大一统模型——T5&#xff0c;同样是数据和实验多得让你瞠目结舌的论文&#xff0c;没错&#xff0c;就是在炫富&#xff0c;你有钱你也可以烧啊…

力扣经典150题第五十五题:逆波兰表达式求值

目录 题目描述和要求示例解释解题思路算法实现复杂度分析测试和验证总结和拓展参考资料 题目描述和要求 给你一个字符串数组 tokens&#xff0c;表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式&#xff0c;并返回一个表示表达式值的整数。 注意&#xff1a; 有…