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

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:只出现一次的数字Ⅲ(详解)

题目&#xff1a; 给你一个整数数组 nums&#xff0c;其中恰好有两个元素只出现一次&#xff0c;其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。 示例 1&…...

【vue3.0 使用组合式定义组件】

Vue3.0 中通过使用 setup 函数来定义组件。setup 函数接收两个参数&#xff0c;第一个参数是组件的 props&#xff0c;第二个参数是一个上下文对象&#xff0c;可以通过它访问到与组件相关的数据和方法。在 setup 函数中&#xff0c;我们可以使用 Vue3.0 提供的新特性 — 组合式…...

Tensor-动手学深度学习-李沐_笔记

介绍 Tensor&#xff0c;又称"张量"&#xff0c;其实就是n维度数组。不同维度的Tensor示意图如下&#xff1a; 关于Tensor.reshape reshape函数可以处理总元素个数相同的任何新形状&#xff0c;【3&#xff0c;2&#xff0c;5】->【3&#xff0c;10】->【5&a…...

Kafka生产者原理 kafka生产者发送流程 kafka消息发送到集群步骤 kafka如何发送消息 kafka详解

kafka尚硅谷视频&#xff1a; 10_尚硅谷_Kafka_生产者_原理_哔哩哔哩_bilibili ​ 1. producer初始化&#xff1a;加载默认配置&#xff0c;以及配置的参数&#xff0c;开启网络线程 2. 拦截器拦截 3. 序列化器进行消息key, value序列化 4. 进行分区 5. kafka broker集群 获取…...

Uniapp笔记(七)uniapp打包

一、项目打包 1、h5打包 登录dcloud账户&#xff0c;在manifest.json的基础配置选项中&#xff0c;点击重新获取uniapp应用标识APPID 在manifest.json的Web配置选项的运行的基础路径中输入./ 在菜单栏的发行栏目&#xff0c;点击网站-PC或手机H5 输入网站标题和网站域名&am…...

软考高级系统架构设计师系列论文七十六:论基于构件的软件开发

软考高级系统架构设计师系列论文七十六:论基于构件的软件开发 一、构件相关知识点二、摘要三、正文四、总结一、构件相关知识点 软考高级系统架构设计师系列之:面向构件的软件设计,构件平台与典型架构...

基于Thinkphp6框架全新UI的AI网址导航系统源码

2023全新UI的AI网址导航系统源码&#xff0c;基于thinkphp6框架开发的 AI 网址导航是一个非常实用的工具&#xff0c;它能够帮助用户方便地浏览和管理自己喜欢的网站。 相比于其他的 AI 网址导航&#xff0c;这个项目使用了更加友好和易用的 ThinkPHP 框架进行搭建&#xff0c;…...

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编译出来的程序无法在其它电脑上运行

在其它电脑&#xff08;比如Windows Server 2012&#xff09;上运行Visual Studio编译出来的应用程序&#xff0c;结果报错&#xff1a;“无法启动此程序&#xff0c;因为计算机中丢失VCRUNTIME140.dll。尝试重新安装该程序以解决此问题。” 解决方法&#xff1a; 属性 -> …...

习题练习 C语言(暑期第二弹)

编程能力小提升&#xff01; 前言一、表达式判断二、Assii码的理解应用三、循环跳出判断四、数字在升序数组中出现的次数五、整数转换六、循环语句的应用七、函数调用八、两个数组的交集九、C语言基础十、图片整理十一、数组的引用十二、数组的引用十三、字符个数统计十四、多数…...

树莓派使用Nginx+cpolar内网穿透实现无公网IP访问内网本地站点

文章目录 1. Nginx安装2. 安装cpolar3.配置域名访问Nginx4. 固定域名访问5. 配置静态站点 安装 Nginx&#xff08;发音为“engine-x”&#xff09;可以将您的树莓派变成一个强大的 Web 服务器&#xff0c;可以用于托管网站或 Web 应用程序。相比其他 Web 服务器&#xff0c;Ngi…...

攻防世界-Web_php_unserialize

原题 解题思路 注释说了flag存在f14g.php中&#xff0c;但是在wakeup函数中&#xff0c;会把传入的文件名变成index.php。看wp知道&#xff0c;如果被反序列话的字符串其中对应的对象的属性个数发生变化时&#xff0c;会导致反序列化失败而同时使得__wakeup 失效&#xff08;CV…...

云化背景下的接口测试覆盖率自动化检查

一、问题来源 在云化场景下&#xff0c;API的测试覆盖是一项重要评估与考察指标。除了开发者自测试外&#xff08;UT&#xff09;&#xff0c;还可以利用云化测试平台、流水线等方法进行相关指标的检查与考核。利用这种方法既可以减轻开发者测试工作量&#xff0c;不必在本地做…...

QCC_BES 音频重采样算法实现

+V hezkz17进数字音频系统研究开发交流答疑群(课题组) 这段代码是一个用于将音频数据进行立体声重采样的函数。以下是对代码的解读: 函数接受以下参数: pcm_buf:16位有符号整型的音频缓冲区,存储了输入的音频数据。pcm_len:音频缓冲区的长度。mic1:16位有符号整型的音频…...

如何使用CSS实现一个3D旋转效果?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 3D效果实现⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域…...

联想电脑装系统无法按F9后无法从系统盘启动的解决方案

开机时按F9发现没有加载系统盘. 打开BIOS设置界面&#xff0c;调整设置如下: BOOT MODE: Legacy Support.允许legacy方式boot. BOOT PRIORITY: Legacy First. Legacy方式作为首选的boot方式. USB BOOT: ENABLED. 允许以usb方式boot. Legacy: 这里设置legacy boot的优先级,…...

AMEYA360:大唐恩智浦电池管理芯片DNB1168-新能源汽车BMS系统的选择

DNB1168是一款全球独有的集成&#xff08;EIS&#xff09;交流阻抗谱监测功能的单电池监测芯片。该芯片通过车规级AEC-Q100和汽车行业最高功能安全等级ISO 26262&#xff1a;2018 ASIL-D双重认证。芯片?内部集成多种高精度电池参数监测&#xff0c;支持电压、温度、交流阻抗检…...

【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 控制⭐ 注意事项&#xff1a;⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff0…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...