leetcode:只出现一次的数字Ⅲ(详解)
题目:
给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
示例 1:
输入:nums = [1,2,1,3,2,5] 输出:[3,5] 解释:[5, 3] 也是有效的答案。
示例 2:
输入:nums = [-1,0] 输出:[-1,0]
示例 3:
输入:nums = [0,1] 输出:[1,0]
提示:
2 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1- 除两个只出现一次的整数外,
nums中的其他数字都出现两次
思路:
1 所有数字异或,结果是只出现一次的两个数字的异或结果
(异或:相同为0,相异为1,0与任何数异或都是数字本身)
2 得到答案的两个数字异或的结果,区分这两个数字:
(这两个数字互不相同,则一定在某些二进制位上,一个数字是1,另一个数字则对应是0)
异或的结果,它所有的二进制位中一定存在二进制位为1的,此位置的二进制位就可以区分
a 在异或结果中找到一个可以区分两个数字的二进制位
数字&(-数字):可以得到此数字二进制位中最低位的1,这里称之为j
那么异或结果&(-异或结果):就是异或结果二进制位中最低位的1
注意:若异或结果是INT_MIN,即(-2147483648)
原码: 1000 0000 0000 0000 0000 0000 0000 0000
用于位运算的补码溢出了
所以当异或结果为INT_MIN时,异或结果本身就是最低位的1,不用进行位运算
INT_MAX :0111 1111 1111 1111 1111 1111 1111 1111
-INT_MAX的补码:1000 0000 0000 0000 0000 0000 0000 0001
都没有溢出,所以INT_MAX是可以进行位运算来获取INT_MAX二进制中最低位的1
如:3: 00000000 00000000 00000000 00000011(整数的原码,反码,补码都相同)
-3的原码: 10000000 00000000 00000000 00000011(位运算都要用补码)
-3的反码: 11111111 11111111 11111111 11111100(原码的符号位不变,其他位按位取反)
-3的补码: 11111111 11111111 11111111 11111101(补码+1)
3&(-3):00000000 00000000 00000000 00000011
& 11111111 11111111 11111111 11111101
结果: 00000000 00000000 00000000 00000001(3最低位的那个1)
再如:

b 根据j,将所有数字划分成两个阵营,分别异或在一起
出现两次的数字一定在同一阵营,异或一定为0
某数字&j为1:表示此数字在作为区分的二进制位上数值为1
某数字&j为0:表示此数字在作为区分的二进制位上数值为0
最终两阵营的结果就是两个答案了
代码实现:
class Solution
{
public:vector<int> singleNumber(vector<int>& nums){int k = 0;//所有数字异或的结果for(auto e:nums){k^=e;}int j =k==INT_MIN?k: k&(-k);//异或结果二进制中最低位的1int ret1 = 0;int ret2 = 0;for(auto e:nums){if(e&j)//在作为区分的二进制上数值为1{ret1^=e;}else在作为区分的二进制上数值为0{ret2^=e;}}return {ret1,ret2};}
};
相关文章:
leetcode:只出现一次的数字Ⅲ(详解)
题目: 给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。 示例 1&…...
【vue3.0 使用组合式定义组件】
Vue3.0 中通过使用 setup 函数来定义组件。setup 函数接收两个参数,第一个参数是组件的 props,第二个参数是一个上下文对象,可以通过它访问到与组件相关的数据和方法。在 setup 函数中,我们可以使用 Vue3.0 提供的新特性 — 组合式…...
Tensor-动手学深度学习-李沐_笔记
介绍 Tensor,又称"张量",其实就是n维度数组。不同维度的Tensor示意图如下: 关于Tensor.reshape reshape函数可以处理总元素个数相同的任何新形状,【3,2,5】->【3,10】->【5&a…...
Kafka生产者原理 kafka生产者发送流程 kafka消息发送到集群步骤 kafka如何发送消息 kafka详解
kafka尚硅谷视频: 10_尚硅谷_Kafka_生产者_原理_哔哩哔哩_bilibili 1. producer初始化:加载默认配置,以及配置的参数,开启网络线程 2. 拦截器拦截 3. 序列化器进行消息key, value序列化 4. 进行分区 5. kafka broker集群 获取…...
Uniapp笔记(七)uniapp打包
一、项目打包 1、h5打包 登录dcloud账户,在manifest.json的基础配置选项中,点击重新获取uniapp应用标识APPID 在manifest.json的Web配置选项的运行的基础路径中输入./ 在菜单栏的发行栏目,点击网站-PC或手机H5 输入网站标题和网站域名&am…...
软考高级系统架构设计师系列论文七十六:论基于构件的软件开发
软考高级系统架构设计师系列论文七十六:论基于构件的软件开发 一、构件相关知识点二、摘要三、正文四、总结一、构件相关知识点 软考高级系统架构设计师系列之:面向构件的软件设计,构件平台与典型架构...
基于Thinkphp6框架全新UI的AI网址导航系统源码
2023全新UI的AI网址导航系统源码,基于thinkphp6框架开发的 AI 网址导航是一个非常实用的工具,它能够帮助用户方便地浏览和管理自己喜欢的网站。 相比于其他的 AI 网址导航,这个项目使用了更加友好和易用的 ThinkPHP 框架进行搭建,…...
Html 补充
accesskey 设置快捷键 Alt设定的键 <a href"https://blog.csdn.net/lcatake/article/details/131716967?spm1001.2014.3001.5501" target"_blank" accesskey"i">我的博客</a> contenteditable 使文本可编译 默认为false 对输入框无…...
Visual Studio编译出来的程序无法在其它电脑上运行
在其它电脑(比如Windows Server 2012)上运行Visual Studio编译出来的应用程序,结果报错:“无法启动此程序,因为计算机中丢失VCRUNTIME140.dll。尝试重新安装该程序以解决此问题。” 解决方法: 属性 -> …...
习题练习 C语言(暑期第二弹)
编程能力小提升! 前言一、表达式判断二、Assii码的理解应用三、循环跳出判断四、数字在升序数组中出现的次数五、整数转换六、循环语句的应用七、函数调用八、两个数组的交集九、C语言基础十、图片整理十一、数组的引用十二、数组的引用十三、字符个数统计十四、多数…...
树莓派使用Nginx+cpolar内网穿透实现无公网IP访问内网本地站点
文章目录 1. Nginx安装2. 安装cpolar3.配置域名访问Nginx4. 固定域名访问5. 配置静态站点 安装 Nginx(发音为“engine-x”)可以将您的树莓派变成一个强大的 Web 服务器,可以用于托管网站或 Web 应用程序。相比其他 Web 服务器,Ngi…...
攻防世界-Web_php_unserialize
原题 解题思路 注释说了flag存在f14g.php中,但是在wakeup函数中,会把传入的文件名变成index.php。看wp知道,如果被反序列话的字符串其中对应的对象的属性个数发生变化时,会导致反序列化失败而同时使得__wakeup 失效(CV…...
云化背景下的接口测试覆盖率自动化检查
一、问题来源 在云化场景下,API的测试覆盖是一项重要评估与考察指标。除了开发者自测试外(UT),还可以利用云化测试平台、流水线等方法进行相关指标的检查与考核。利用这种方法既可以减轻开发者测试工作量,不必在本地做…...
QCC_BES 音频重采样算法实现
+V hezkz17进数字音频系统研究开发交流答疑群(课题组) 这段代码是一个用于将音频数据进行立体声重采样的函数。以下是对代码的解读: 函数接受以下参数: pcm_buf:16位有符号整型的音频缓冲区,存储了输入的音频数据。pcm_len:音频缓冲区的长度。mic1:16位有符号整型的音频…...
如何使用CSS实现一个3D旋转效果?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 3D效果实现⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域…...
联想电脑装系统无法按F9后无法从系统盘启动的解决方案
开机时按F9发现没有加载系统盘. 打开BIOS设置界面,调整设置如下: BOOT MODE: Legacy Support.允许legacy方式boot. BOOT PRIORITY: Legacy First. Legacy方式作为首选的boot方式. USB BOOT: ENABLED. 允许以usb方式boot. Legacy: 这里设置legacy boot的优先级,…...
AMEYA360:大唐恩智浦电池管理芯片DNB1168-新能源汽车BMS系统的选择
DNB1168是一款全球独有的集成(EIS)交流阻抗谱监测功能的单电池监测芯片。该芯片通过车规级AEC-Q100和汽车行业最高功能安全等级ISO 26262:2018 ASIL-D双重认证。芯片?内部集成多种高精度电池参数监测,支持电压、温度、交流阻抗检…...
【Python进阶学习】【Excel读写】使用openpyxl写入xlsx文件
1、当前文件不存在指定的子文件夹则创建 2、文件存在追加写入 3、文件不存在创建文件并写入表头 # -*- coding: utf-8 -*- import openpyxl as xl import osdef write_excel_file(folder_path):if not os.path.exists(folder_path):os.makedirs(folder_path)result_path os.p…...
Docker(md版)
Docker 一、Docker二、更换apt源三、docker搭建四、停启管理五、配置加速器5.1、方法一5.2、方法二 六、使用docker运行漏洞靶场1、拉取tomcat8镜像2、拉取成功3、开启服务4、查看kali的IP地址5、访问靶场6、关闭漏洞靶场 七、vulapps靶场搭建 一、Docker Docker是一个开源的应…...
如何使用CSS实现一个无限循环滚动的图片轮播效果?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐HTML 结构⭐ CSS 样式⭐ JavaScript 控制⭐ 注意事项:⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅࿰…...
D2DX暗黑2宽屏补丁:3分钟让经典游戏焕发新生的终极优化方案
D2DX暗黑2宽屏补丁:3分钟让经典游戏焕发新生的终极优化方案 【免费下载链接】d2dx D2DX is a complete solution to make Diablo II run well on modern PCs, with high fps and better resolutions. 项目地址: https://gitcode.com/gh_mirrors/d2/d2dx 还在…...
Windows极速ADB驱动一键安装:告别繁琐配置的终极指南
Windows极速ADB驱动一键安装:告别繁琐配置的终极指南 【免费下载链接】Latest-adb-fastboot-installer-for-windows A Simple Android Driver installer tool for windows (Always installs the latest version) 项目地址: https://gitcode.com/gh_mirrors/la/Lat…...
【资讯】《二〇二五年中国知识产权保护状况》白皮书正式发布
2026年5月7日,《二〇二五年中国知识产权保护状况》白皮书正式发布,呈现了2025年中国知识产权保护工作进展,系统介绍制度建设、审批登记、文化建设、国际合作等方面的扎实成果,为社会各界和国际社会了解中国知识产权保护最新实践提…...
AI应用开发利器:NeuroAPI网关统一管理多模型调用与部署实战
1. 项目概述:一个面向AI应用开发的API网关最近在折腾AI应用开发的朋友,估计都绕不开一个头疼的问题:模型管理。今天想试试Claude,明天项目需要接入GPT-4,后天可能又要调用一个开源的Llama模型。每个模型都有自己的API地…...
2026 断桥铝系统门窗选购指南:品牌综合实力榜与技术选型要点
2026 断桥铝系统门窗选购指南:品牌综合实力榜与技术选型要点行业发展背景与产品技术迭代中国住宅装饰装修产业正向品质化、精细化与绿色化深度转型,居住者对建筑外围护结构的综合性能要求持续攀升。传统非系统化断桥铝门窗因结构设计单一、性能指标离散、…...
[GESP202512 C++ 三级] 判断题第 9 题
【题目描述】 给定一个正整数 a ,当需要计算 -a 的补码时,有这样一个计算技巧:将 a 的二进制形式从右往左扫描,遇到第一个 1 之后,将找到的第一个 1 左边的所有位都取反,能得到 -a 的补码。 答:…...
手把手教你用TI TICS Pro配置LMX2594时钟芯片(附寄存器导出与SPI写入指南)
手把手教你用TI TICS Pro配置LMX2594时钟芯片(附寄存器导出与SPI写入指南) 在高速数字系统设计中,时钟信号的稳定性和精确度往往决定着整个系统的性能上限。作为射频与通信领域的工程师,我深刻体会过时钟配置失误带来的调试噩梦—…...
别再只盯着波形了!用IC617的gmid曲线,帮你快速评估工艺角下的MOS管性能
用gmid曲线簇破解工艺角难题:IC617高效评估MOS性能实战 在模拟电路设计的江湖里,工艺角(PVT)分析就像一场永无止境的攻防战。每次流片前,工程师们都要面对那个灵魂拷问:"这个偏置点在FF/SS角落下会不会…...
别再傻傻分不清了!数字IC面试必问的Latch与Flip-Flop,我用Verilog代码给你讲明白
数字IC面试突围:Latch与Flip-Flop的Verilog避坑指南 1. 从门电路到时序逻辑:存储单元的本质差异 在数字电路设计中,存储单元如同城市交通的信号灯系统。锁存器(Latch)就像持续亮着的红灯——只要信号有效(电…...
aztfexport扩展开发:如何自定义资源映射和导入逻辑
aztfexport扩展开发:如何自定义资源映射和导入逻辑 【免费下载链接】aztfexport A tool to bring existing Azure resources under Terraforms management 项目地址: https://gitcode.com/gh_mirrors/az/aztfexport Azure Export for Terraform(a…...
