当前位置: 首页 > 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…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...

FOPLP vs CoWoS

以下是 FOPLP&#xff08;Fan-out panel-level packaging 扇出型面板级封装&#xff09;与 CoWoS&#xff08;Chip on Wafer on Substrate&#xff09;两种先进封装技术的详细对比分析&#xff0c;涵盖技术原理、性能、成本、应用场景及市场趋势等维度&#xff1a; 一、技术原…...