LeetCode算法位运算—只出现一次的数字
目录
136. 只出现一次的数字 - 力扣(LeetCode)
解题思路:
代码:
运行结果:
补充
异或的重要性质
136. 只出现一次的数字 - 力扣(LeetCode)
给你一个 非空 整数数组
nums,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
示例 1 :
输入:nums = [2,2,1] 输出:1示例 2 :
输入:nums = [4,1,2,1,2] 输出:4示例 3 :
输入:nums = [1] 输出:1提示:
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外,其余每个元素均出现两次。
解题思路:异或运算(^)的性质:
- 异或运算满足交换律和结合律,即a^b^c = a^(b^c)。
- 对于任何数x,x^x=0,即一个数与自己异或的结果为0。
- 对于任何数x,x^0=x,即一个数与0异或的结果为它本身。
考虑到这些性质,让我们看一下代码的执行过程:
- 初始化变量a为0。
- 遍历数组nums中的每个元素:
- 将a与当前元素进行异或操作,即a^=nums[i]。
- 异或操作会将出现两次的数字消除,因为两个相同的数字异或的结果为0。
- 异或操作会将只出现一次的数字留下,因为任何数字与0异或的结果为它本身。
- 最终,a将保留只出现一次的数字。
- 返回变量a作为结果。
现在,让我们通过一个案例来解析这段代码:
假设输入数组nums为[2, 4, 2, 1, 4],其中只有数字1只出现一次,其他数字都出现了两次。
执行过程如下:
- 初始化变量a为0。
- 遍历数组nums:
- 第一次循环:a^=2,a的值变为2。
- 第二次循环:a^=4,a的值变为6。
- 第三次循环:a^=2,a的值变为4。
- 第四次循环:a^=1,a的值变为5。
- 第五次循环:a^=4,a的值变为1。
- 返回a的值1作为结果。
代码:class Solution {public int singleNumber(int[] nums) {int a=0;for(int i=0;i<nums.length;i++){a^=nums[i];}return a;} }
运行结果:
补充
异或的重要性质
结合律:异或运算满足结合律,即对于任意三个数a、b和c,满足 (a ^ b) ^ c = a ^ (b ^ c)。
自反性:任何数与自身进行异或运算的结果为0,即 a ^ a = 0。这是因为异或运算可以看作是"无进位相加",而相同的位进行异或运算结果为0。
零元素:0是异或运算的零元素,即对于任何数a,满足 a ^ 0 = a。这是因为异或运算中,任何数与0进行异或运算结果为它本身。
逆元素:每个数在异或运算中都有逆元素,即对于任何数a,存在一个数b,满足 a ^ b = 0。这意味着可以通过异或运算来撤销一个数的影响。
消除相同元素:当数组中有成对出现的相同元素时,对整个数组进行异或运算,最终结果为0。这是因为相同元素异或的结果为0,而异或运算满足交换律和结合律。
这些性质使得异或运算在很多场景下非常有用,例如查找只出现一次的数字、判断两个数是否相等、交换两个变量的值等。通过利用这些性质,可以简化问题的处理和求解。
相关文章:
LeetCode算法位运算—只出现一次的数字
目录 136. 只出现一次的数字 - 力扣(LeetCode) 解题思路: 代码: 运行结果: 补充 异或的重要性质 136. 只出现一次的数字 - 力扣(LeetCode) 给你一个 非空 整数数组 nums ,除了某…...
vcpkg manifest 的使用
最近项目上要使用 CMakeLists 管理,由于 Windows 版本有依赖到 vcpkg 提供的库,所以需要使用 vcpkg manifest 来统一设置库的版本,方便后续维护 推荐一个文章,介绍的可以说是非常全面了 VCPKG 特性 - Versioning 不过里面也有一些…...
选择什么电容笔比较好?平板手写笔推荐
由于苹果Pencil的热销,让华国内市场上,也出现了不少的平替式电容笔,这些产品,有好有坏,价格也很公道。不过,也有很多产品的价格都很平价。我是一个拥有多年经验的数码发烧友,在前几年就开始用上…...
pdf转二维码怎么做?pdf二维码制作简单技巧
pdf是一种很常见的文件储存格式,一般通知、发票、简历都会保存为这种格式来使用,那么需要将pdf格式文件做成二维码,该用什么方式来制作呢?下面给大家分享一个pdf转二维码的在线工具,可以通过上传文件一键生成二维码&am…...
【CANoe】TX Self-ACK自应答配置与CPAL实现
一、引言 在测试CAN&CANFD通信或者网络管理的时候,我们经常遇到使用报文(网络管理报文或者通信报文)唤醒被测件这个测试点,如果测试比较多的情况下,我们就会发现,如果CANoe没有接被测件或者被测件没有…...
(Python)MATLAB mat矩阵和Python npy矩阵转换
Python np.ndarray矩阵转换为MATLAB mat文件 import numpy as npimport scipy.io as iomat_path mat_save_pathmat np.zeros([6, 128])io.savemat(mat_path, {name: mat})Python读取MATLAB mat文件 import numpy as np from scipy import iomat io.loadmat(your_mat_file.…...
Flink1.14 SourceReader概念入门讲解与源码解析 (三)
目录 SourceReader 概念 SourceReader 源码方法 void start(); InputStatus pollNext(ReaderOutput output) throws Exception; List snapshotState(long checkpointId); CompletableFuture isAvailable(); void addSplits(List splits); 参考 SourceReader 概念 Sour…...
PS运行中缺失d3dcompiler_47.dll问题的5个有效修复方法总结
在使用ps作图的时候,我们有时会遇到一些问题,其中之一就是“PS运行中缺失d3dcompiler_47.dll”的问题。这个问题可能会导致PS无法正常运行,“d3dcompiler_47.dll”。这是一个动态链接库文件,它是DirectX的一部分,主要负…...
【MATLAB-Retinex图像增强算法的去雾技术】
续:【MATLAB-基于直方图优化的图像去雾技术】 【MATLAB-Retinex图像增强算法的去雾技术】 1 原图2 MATLAB实现代码3 结果图示 参考书籍:计算机视觉与深度学习实战:以MATLAB、Python为工具, 主编:刘衍琦, 詹福宇, 王德建…...
使用 2 个 HSplitView 在 swiftUI 中创建一个 3 窗格界面
Pet*_*ter 8 嗯,我会的。在断断续续地挣扎了几个星期之后,在我问这个问题一个小时后,我似乎解决了它!只需将第二个 HSplitView 的 layoutPriority 设置为 1,并将中心视图也设置为 1。当你想到它时是有道理的࿱…...
【C++ 操作符重载:定制自己的运算符行为】
在C编程中,操作符重载是一项强大的特性,它允许程序员定制内置运算符的行为,使它们适用于用户自定义的数据类型。这篇博客将介绍什么是操作符重载,如何使用它,以及一些最佳实践。 什么是操作符重载? 操作符…...
Android Fragment 基本概念和基本使用
Android Fragment 基本概念和基本使用 一、基本概念 Fragment,简称碎片,是Android 3.0(API 11)提出的,为了兼容低版本,support-v4库中也开发了一套Fragment API,最低兼容Android 1.6。 过去s…...
xml schema中的all元素
说明 xml schema中的all元素表示其中的子元素可以按照任何顺序出现,每个元素可以出现0次或者1次。 https://www.w3.org/TR/xmlschema-1/#element-all maxOccurs的默认值是1,minOccurs 的默认值是1。 举例 <element name"TradePriceRequest&…...
Java8实战-总结42
Java8实战-总结42 用Optional取代null应用 Optional 的几种模式默认行为及解引用 Optional 对象两个 Optional 对象的组合使用 filter 剔除特定的值 用Optional取代null 应用 Optional 的几种模式 默认行为及解引用 Optional 对象 采用orElse方法读取这个变量的值࿰…...
实现日期间的运算——C++
😶🌫️Take your time ! 😶🌫️ 💥个人主页:🔥🔥🔥大魔王🔥🔥🔥 💥代码仓库:🔥🔥魔…...
云上攻防-云原生篇K8s安全Config泄漏Etcd存储Dashboard鉴权Proxy暴露
文章目录 云原生-K8s安全-etcd未授权访问云原生-K8s安全-Dashboard未授权访问云原生-K8s安全-Configfile鉴权文件泄漏云原生-K8s安全-Kubectl Proxy不安全配置 云原生-K8s安全-etcd未授权访问 攻击2379端口:默认通过证书认证,主要存放节点的数据&#x…...
ChatGPT 的工作原理学习 难以理解 需要先找个容易的课来跟下。
ChatGPT 的工作原理 传统搜超搜引擎原理:蜘蛛抓取和数据收集,用户交互查找。 ChatGPT 的工作原理:数据收集称为预训练,用户响应阶段称为推理。 ChatGPT是一种基于自然语言处理技术的人工智能模型,它的工作原理建立在…...
5.DApp-前端网页怎么连接MetaMask
题记 在前端网页连接metamask,以下是全部操作流程和代码。 编写index.html文件 index.html文件如下: <!DOCTYPE html> <html> <head> <title>My DApp</title> <!--导入用于检测Metamask提供者的JavaScript库--> &l…...
手机应用app打开游戏显示连接服务器失败是什么原因?排查解决方案?
亲爱的同学们,有时候我们在使用手机设备时,可能会遇到一个很头疼的问题——连接服务器失败。这个问题不仅让我们感到困扰,还影响到了我们的用户体验。那么,我们究竟能如何解决这个问题呢?今天,笔者就和大家…...
【Java学习之道】指引篇:从入门到入世
引言 你是否曾为找不到适合自己的Java学习之路而烦恼?是否想摆脱混乱的Java知识体系,找到一条从入门到精通的捷径?来《Java学习之道》吧,本专栏为你量身打造,让我们一起轻松踏上Java学习之旅! 第一章、Jav…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
