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

LeetCode题练习与总结:只出现一次的数字--136

一、题目描述

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

示例 1 :

输入:nums = [2,2,1]
输出:1

示例 2 :

输入:nums = [4,1,2,1,2]
输出:4

示例 3 :

输入:nums = [1]
输出:1

提示:

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • 除了某个元素只出现一次以外,其余每个元素均出现两次。

二、解题思路

这个问题可以通过异或(XOR)操作来解决。异或运算有几个特点:

  1. 任何数和0做异或运算,结果仍然是原来的数,即 a ⊕ 0 = a
  2. 任何数和其自身做异或运算,结果是0,即 a ⊕ a = 0
  3. 异或运算满足交换律和结合律,即 a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b

根据以上性质,我们可以将数组中的所有元素进行异或运算。成对的元素异或的结果会是0,最终剩下的结果就是只出现一次的那个元素。

三、具体代码

class Solution {public int singleNumber(int[] nums) {int result = 0;for (int num : nums) {result ^= num;}return result;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

时间复杂度是指算法执行的时间随着输入数据量的增加而增长的速度。在这个问题中,我们关注的是算法执行的基本操作次数。

  • 初始化操作: int result = 0; 这条语句执行了一次,因此它的复杂度是 O(1)。
  • 循环操作: for (int num : nums) { result ^= num; } 这条循环语句会执行 n 次,其中 n 是数组 nums 的长度。循环体中的异或操作 result ^= num 是一个常数时间的操作,因此每次迭代的复杂度是 O(1)。
  • 返回操作: return result; 这条语句执行了一次,因此它的复杂度是 O(1)。

总时间复杂度: 将所有操作的时间复杂度相加,我们得到总的时间复杂度是 O(1) + O(n) + O(1),由于 O(1) 可以忽略不计,因此总的时间复杂度是 O(n)。

2. 空间复杂度

空间复杂度是指算法在执行过程中临时占用存储空间的大小,它是输入数据量的大小的函数。在这个问题中,我们需要考虑算法中使用的额外空间。

  • 变量空间: int result; 这条语句定义了一个整数变量 result,它占用的空间是常数大小的,与输入数组 nums 的大小无关。因此,它的空间复杂度是 O(1)。

总空间复杂度: 将所有操作的空间复杂度相加,我们得到总的空间复杂度是 O(1)。

这个算法非常高效,因为它在线性时间内解决了问题,并且只使用了固定空间

五、总结知识点

  1. 异或运算(XOR):这是代码中的核心概念。异或运算有几个关键特性:任何数与0异或结果为该数本身(a ⊕ 0 = a),任何数与自身异或结果为0(a ⊕ a = 0),异或运算满足交换律和结合律(a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b)。这些特性使得异或运算可以用于解决只出现一次的元素问题。

  2. 数组的遍历:代码中使用增强型for循环(for (int num : nums))来遍历数组nums中的每个元素。这是一种简洁的遍历数组元素的方式。

  3. 位操作:异或运算是一种位操作,它对两个数的每一位进行比较,如果相同则结果为0,不同则结果为1。位操作是解决许多算法问题的强大工具,尤其是在处理位级操作或优化空间复杂度时。

  4. 线性时间复杂度:代码中的循环确保了算法的时间复杂度为O(n),这意味着算法的运行时间与输入数组的大小成线性关系。

  5. 常量空间复杂度:代码中只使用了一个整数变量result来存储最终结果,不随输入数组的大小而变化,因此算法的空间复杂度为O(1)。

  6. 算法设计:代码展示了如何利用数学性质来设计高效的算法。通过理解和应用异或运算的特性,可以在线性时间内找到只出现一次的元素,而不需要额外的空间。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

相关文章:

LeetCode题练习与总结:只出现一次的数字--136

一、题目描述 给你一个 非空 整数数组 nums &#xff0c;除了某个元素只出现一次以外&#xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题&#xff0c;且该算法只使用常量额外空间。 示例 1 &#xff1a; …...

常见的中间件都在解决什么问题?

常见的中间件都在解决什么问题 RocketMQ RocketMQ 是一款功能强大的分布式消息系统。 RocketMQ 源码地址&#xff1a;https://github.com/apache/rocketmq(opens new window) RocketMQ 官方网站&#xff1a;https://rocketmq.apache.org 什么场景下用 RocketMQ&#xff1f…...

微信小程序-scroll-view实现上拉加载和下拉刷新

一.scroll-view实现上拉加载 scroll-view组件通过自身一些属性实现上拉加载的功能。 lower-threshold“100"属性表示距离底部多少px就会实现触发下拉加载的事件。 类似于在.json文件里面配置"onReachBottomDistance”: 100 bindscrolltolower"getMore"属…...

TS中interface和type的区别

在 TypeScript 中&#xff0c;interface 和 type 都可以用来定义对象的类型&#xff0c;但它们之间存在一些差异。 以下是 interface 和 type 的主要区别&#xff1a; 扩展&#xff08;Extending&#xff09;: interface 可以通过 extends 关键字来扩展其他 interface。interfa…...

Hightec编译器系列之高级调试技巧精华总结

Hightec编译器系列之高级调试技巧精华总结 小T为了便于大家理解&#xff0c;本文的思维导图大纲如下&#xff1a; 之前可能很多小伙伴没有使用过Hightec编译器&#xff0c;大家可以参考小T之前的文章《Hightec编译器系列之白嫖就是爽》可以下载一年试用版本。 小T使用过适配英…...

【论文笔记】LoRA LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS

题目&#xff1a;LoRA: LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS 来源: ICLR 2022 模型名称: LoRA 论文链接: https://arxiv.org/abs/2106.09685 项目链接: https://github.com/microsoft/LoRA 文章目录 摘要引言问题定义现有方法的问题方法将 LORA 应用于 Transformer 实…...

【Sa-Token|4】Sa-Token微服务项目应用

若微服务数量多&#xff0c;如果每个服务都改动&#xff0c;工作量大&#xff0c;则可以只在网关和用户中心进行改动&#xff0c;也是可以实现服务之间的跳转。 这种方式可以通过在网关服务中生成和验证 Sa-Token&#xff0c;并将其与现有的 Token关联存储在 Redis 中。用户中心…...

鸿蒙开发系统基础能力:【@ohos.hilog (日志打印)】

日志打印 hilog日志系统&#xff0c;使应用/服务可以按照指定级别、标识和格式字符串输出日志内容&#xff0c;帮助开发者了解应用/服务的运行状态&#xff0c;更好地调试程序。 说明&#xff1a; 本模块首批接口从API version 7开始支持。后续版本的新增接口&#xff0c;采用…...

SpringMVC系列十: 中文乱码处理与JSON处理

文章目录 中文乱码处理自定义中文乱码过滤器Spring提供的过滤器处理中文 处理json和HttpMessageConverter<T>处理JSON-ResponseBody处理JSON-RequestBody处理JSON-注意事项和细节HttpMessageConverter<T\>文件下载-ResponseEntity<T\>作业布置 上一讲, 我们学…...

使用MyBatisPlus进行字段的自动填充

使用MyBatisPlus进行字段的自动填充 需求场景 当我们往数据库里面插入一条数据&#xff0c;或者是更新一条数据时&#xff0c;一般都需要标记创建时间create_time和更新时间update_time的值&#xff0c;但是如果我们每张表的每个请求&#xff0c;在执行sql语句的时候我们都手…...

python爬虫之aiohttp多任务异步爬虫

python爬虫之aiohttp多任务异步爬虫 爬取的flash服务如下&#xff1a; from flask import Flask import timeapp Flask(__name__)app.route(/bobo) def index_bobo():time.sleep(2)return Hello boboapp.route(/jay) def index_jay():time.sleep(2)return Hello jayapp.rout…...

1964springboot VUE小程序在线学习管理系统开发mysql数据库uniapp开发java编程计算机网页源码maven项目

一、源码特点 springboot VUE uniapp 小程序 在线学习管理系统是一套完善的完整信息管理类型系统&#xff0c;结合springboot框架uniapp和VUE完成本系统&#xff0c;对理解vue java编程开发语言有帮助系统采用springboot框架&#xff08;MVC模式开发&#xff09;&#xff0c;…...

【前端项目笔记】3 用户管理

用户管理相关功能实现 涉及表单、对话框、Ajax数据请求 基本页面 用户列表开发 在router.js中导入Users.vue 解决用户列表小问题 选中&#xff08;激活&#xff09;子菜单后刷新不显示高亮 给二级菜单绑定单击事件&#xff0c;点击链接时把对应的地址保存到sessionSto…...

【文献及模型、制图分享】基于SSP-RCP不同情景的京津冀地区土地覆被变化模拟

公众号新功能 目前公众号新增以下等功能 1、处理GIS出图、Python制图、区位图、土地利用现状图、土地利用动态度和重心迁移图等等 2、核密度分析、网络od分析、地形分析、空间分析等等 3、地理加权回归、地理探测器、生态环境质量指数、地理加权回归模型影响因素分析、计算…...

基于单片机的智能台灯控制系统

摘要&#xff1a; 文章设计一款单片机智能台灯控制系统&#xff0c;实现对台灯的手动和自动控制功能&#xff0c;以 STC89C52 单片机作为多功能智能台灯的主控制器&#xff0c;光电检测模块检测坐姿&#xff0c;红外传感器检测人体&#xff0c;光敏电阻检测光强&#xff0c;同…...

PrestaShop的一些使用介绍

目录 PrestaShop 是一个功能丰富的开源电子商务解决方案。 1. 以下是其基本概念和架构的一些要点&#xff1a; 2. PrestaShop 的模块开发是扩展其功能的重要方式。以下是对 PrestaShop 模块开发的详细介绍&#xff1a; 开发环境准备&#xff1a; 3. PrestaShop 的模块开发允…...

零基础女生如何入门人工智能,从哪里下手?学习时间大概要多久?

作为一个理工科早期毕业生&#xff0c;出于近乎本能的敏感&#xff0c;格外关注全网热议的ChatGPT。 本来国内就业环境就不好&#xff0c;各行各业内卷越来越严重&#xff0c;加上人工智能的异军突起&#xff0c;各行各业势必将迎来科技进步跨时代的巨大冲击&#xff0c;在此情…...

简答分享python学习进修网站

一、网战推荐 CodeCombat 是一款网页编程游戏。这款编程游戏借鉴了游戏很多设计元素&#xff0c;游戏剧情十分丰富。Codecombat能够学习Python多种语言&#xff0c;这些语言能够运用到游戏设计、网页应用、app的开发上。 Checkio 是一个基于浏览器的游戏&#xff0c;你需要使…...

linux高级编程(I/O)

fputc int fputc(int c, FILE *stream); 功能: 向流中写入一个字符 参数: c:要写入的字符 stream:文件流指针 返回值: 成功返回写入的字符ASCII码值 失败返回EOF fgetc int fgetc(FILE *stream); 功能: 从流中读取一个字符 参数: stream:文件流…...

Java面试——认证与授权

X、常见面试题汇总 1、Shiro与SpringSecutity对比 1&#xff09;Shiro的特点&#xff1a; Shiro 是 Apache 下的项目&#xff0c;相对简单、轻巧&#xff0c;更容易上手使用。 Shiro 权限功能基本都能满足&#xff0c;单点登录都可以实现。且不用与任何的框架或者容器绑定, 可…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#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. 执行器…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...