当前位置: 首页 > 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;单点登录都可以实现。且不用与任何的框架或者容器绑定, 可…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

Monorepo架构: Nx Cloud 扩展能力与缓存加速

借助 Nx Cloud 实现项目协同与加速构建 1 &#xff09; 缓存工作原理分析 在了解了本地缓存和远程缓存之后&#xff0c;我们来探究缓存是如何工作的。以计算文件的哈希串为例&#xff0c;若后续运行任务时文件哈希串未变&#xff0c;系统会直接使用对应的输出和制品文件。 2 …...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...

土建施工员考试:建筑施工技术重点知识有哪些?

《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目&#xff0c;核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容&#xff0c;附学习方向和应试技巧&#xff1a; 一、施工组织与进度管理 核心目标&#xff1a; 规…...

大数据治理的常见方式

大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法&#xff0c;以下是几种常见的治理方式&#xff1a; 1. 数据质量管理 核心方法&#xff1a; 数据校验&#xff1a;建立数据校验规则&#xff08;格式、范围、一致性等&#xff09;数据清洗&…...

Windows 下端口占用排查与释放全攻略

Windows 下端口占用排查与释放全攻略​ 在开发和运维过程中&#xff0c;经常会遇到端口被占用的问题&#xff08;如 8080、3306 等常用端口&#xff09;。本文将详细介绍如何通过命令行和图形化界面快速定位并释放被占用的端口&#xff0c;帮助你高效解决此类问题。​ 一、准…...