leetcode:只出现一次的数字 Ⅲ(详解)

news/2024/5/10 5:11:44/文章来源:https://blog.csdn.net/weixin_73142957/article/details/129903382

前言:内容包括:题目,代码实现,大致思路,代码解读

题目:

给你一个整数数组 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]

代码实现:

int* singleNumber(int* nums, int numsSize, int* returnSize)
{int ret = 0;int i = 0;for(i=0;i<numsSize;i++){ret^=nums[i];}int pos = 0;for(i=0;i<32;i++){if(((ret>>i)&1)==1){pos = i;break;}}int*ret2 = (int*)calloc(2,sizeof(int));for(i=0;i<numsSize;i++){if((nums[i]>>pos)&1==1){ret2[0]^=nums[i];}else{ret2[1]^=nums[i];}}*returnSize = 2;return ret2;}

大致思路:

分组异或:

仅有两个数字只出现一次,其他数字均成对出现

异或:相同为0,相异为1

1 数组中的所有数字异或在一起,结果=只出现一次的两个数字异或在一起

   比如:1,2,1,3,2,5

   异或:1^1^2^2^3^5 = 3^5

   3的二进制:0 1 1

   5的二进制:1 0 1

 蓝色圈/红色圈的这一位,若是某个数字在这一位上的值是1,成为一组

                                          若是某个数字在这一位上的值是0,成为另外一组

 

2 将这两个数字分至不同组,每组异或,结果 = 要找的数字

   比如:1,2,1,3,2,5

   分组只需要将只出现过一次的3和5分开即可

   第一组(红色圈的位置上的值为0):1 1 5 异或:1^1^3 = 0^3 = 3

   第二组(红色圈的位置上的值为1):2 2 3  异或:2^2^5 = 0^5 = 5

代码解读:

part1

    int ret = 0;int i = 0;for(i=0;i<numsSize;i++){ret^=nums[i];}

将数组中的所有数字异或在一起,最终只会留下要找的两个数字异或在一起的结果

有了这个结果,我们就能将这两个数字分开至不同的组

part2

    int pos = 0;for(i=0;i<32;i++){if(((ret>>i)&1)==1)//找出能够区分两个仅出现过一次数字的位置{pos = i;break;}}

ret:仅出现过一次的两个数字异或在一起的结果

ret共有32个比特位,每一个比特位都要来到最低位(第i个比特位右移i位来到最低位)与1按位与

按位与:&,两个都是1,则结果为1,只要有一个为0,则结果为0

part3

    int*ret2 = (int*)calloc(2,sizeof(int));for(i=0;i<numsSize;i++){if((nums[i]>>pos)&1==1)//让pos位上的值为1的所有数字异或成为一组{ret2[0]^=nums[i];}else{ret2[1]^=nums[i]; //让让pos位上的值为0的所有数字异或成为一组}}*returnSize = 2;return ret2;

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_283450.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

DOS批处理文件---内嵌参数变量扩充功能

1 内嵌参数变量 1.1 介绍 内嵌参数变量指&#xff1a;%i&#xff0c;其中i为大于等于0的整数。如%0&#xff0c; %1&#xff0c; %2&#xff0c;... 1.2 作用 可以客制化功能。 1.3 案例 批处理文件&#xff1a;main_Param.bat echo off && setlocal ENABLEDELA…

Solidworks学习一

目录页面介绍&#xff1a;视图操作&#xff1a;实例圆柱&#xff1a;直线的绘制&#xff1a;草图的保存和不保存&#xff1a;绘制工具&#xff1a;切线弧&#xff1a;转换实体引用&#xff1a;交叉曲线&#xff1a;等距实体&#xff1a;移动复制&#xff1a;约束&#xff1a;约…

MyBatisPlus-DQL编程控制

MyBatisPlus-DQL编程控制3&#xff0c;DQL编程控制3.1 条件查询3.1.1 条件查询的类3.1.2 环境构建3.1.3 构建条件查询3.1.4 多条件构建3.1.5 null判定3.2 查询投影3.2.1 查询指定字段3.2.2 聚合查询3.2.3 分组查询3.3 查询条件3.3.1 等值查询3.3.2 范围查询3.3.3 模糊查询3.3.4…

一起学 WebGL:动态绘制点

大家好&#xff0c;我是前端西瓜哥。上一篇文章讲解了如何绘制一个点。但这个点的信息是写死在渲染器源码中的&#xff0c;也就是硬编码。 这是系列文章&#xff0c;如果你是初学者&#xff0c;你需要看上一篇文章才好理解这节课的内容。 《一起学 WebGL&#xff1a;绘制一个点…

python五角星编程代码绘制

大家好&#xff0c;我是你们的好朋友&#xff0c;今天继续分享 Python的编程知识。 在 Python中&#xff0c;有一个非常强大的数据可视化工具&#xff1a; database. dl &#xff08;&#xff09;&#xff0c;其中有一个功能就是可以绘制五角星。 什么是五角星&#xff1f; 在数…

jenkins配置插件发版了解

jenkins配置&插件&发版了解 jenkins https://mirrors.jenkins.io/war-stable/2.222.1/ 包下载地址 jenkins镜像源修改 sed -i s/https:\/\/www.google.com/https:\/\/www.baidu.com/g default.json sed -i s/https:\/\/updates.jenkins.io\/download/https:\/\/mi…

怎么使用思维导图?

回答这个问题前&#xff0c;我们先来了解下三个问题&#xff1a; 1.思维导图是什么&#xff1f; 思维导图&#xff0c;又名心智导图&#xff0c;是表达发散性思维的有效图形思维工具 &#xff0c;它简单却又很有效同时又很高效&#xff0c;是一种实用性的思维工具&#xff08…

Ubuntu22.04中安装PyCharm

目录 1. 在ubuntu中下载linux版本的PyCharm。 2. 将下载好的pycharmxxxx.tar.gz文件解压。 3. 在解压后的pycharm文件夹下的bin文件夹下&#xff08;此处为&#xff1a;pycharm-edu-2021.1.2/bin&#xff09;&#xff0c;在空白处右键&#xff0c;然后选择”在终端打开“。然…

蓝桥杯第26天(Python)考前挣扎

题型&#xff1a; 1.思维题/杂题&#xff1a;数学公式&#xff0c;分析题意&#xff0c;找规律 2.BFS/DFS&#xff1a;广搜&#xff08;递归实现&#xff09;&#xff0c;深搜&#xff08;deque实现&#xff09; 3.简单数论&#xff1a;模&#xff0c;素数&#xff08;只需要…

使用 LifseaOS 体验 ACK 千节点分钟级扩容

作者&#xff1a;阿里云 ACK 和操作系统团队 三年前的云栖大会上&#xff0c;LifseaOS 正式发布&#xff0c;这是一款专为云原生场景而垂直优化的操作系统发行版&#xff0c;即业界统称的 ContainerOS。初始发布时&#xff0c;它提供了如下几个突出的特性&#xff1a;轻量&…

guitar pro8.1免费的吉他学习辅助软件

从名字上看就知道这是一款针对吉他谱开发的软件&#xff0c;相信大多数吉他爱好者都用过或者听过这款软件。可以通过鼠标和键盘的操作对吉他谱的内容进行输入&#xff0c;支持四线谱&#xff0c;五线谱、六线谱等曲谱的制作。软件涵盖了几乎所有的吉他演奏技巧符号&#xff0c;…

OpenCV实战(17)——FAST特征点检测

OpenCV实战&#xff08;17&#xff09;——FAST特征点检测0. 前言1. FAST 特征点检测2. 自适应特征检测3. 完整代码小结系列链接0. 前言 Harris 算子根据两个垂直方向上的强度变化率给出了角点(或更一般地说&#xff0c;兴趣点)的数学定义。但使用这种定义需要计算图像导数&am…

Delphi 彻底搞懂 Unix/Linux 时间格式及平台间转换

目录 一、TDateTime 时间格式 二、Unix/Linux的日期和时间格式 三、Delphi中操作Unix/Linux格式的日期和时间 1. TDateTime 转 Unix/Linux格式 2. Unix/Linux格式 转 TDateTime 3. 与腾讯、阿里等平台&#xff08;简称&#xff1a;平台&#xff09;时间转换 四、Delphi…

秋招笔试知识点

1、计算出结构体大小&#xff08;对齐规则&#xff09; struct st { char name; int age; double money; }s; 规则&#xff08;字节对齐&#xff09; 1、 char 从0开始&#xff0c;0是任何数字的整数倍 int 是4个字节&#xff0c;4开始 double 是8个字节&#xff0c;从8开…

人人开源快速搭建后台(踩过的大坑,已解决)

目录 一、renrenfast后端代码导入idea后pom文件中的plugins报错 二、后端yaml配置出现问题 三、启动后端出现404 四、在vscode终端上运行 npm 会询问 “你要如何打开这个文件“ 五、npm install失败 一、renrenfast后端代码导入idea后pom文件中的plugins报错 亲测有效 谷…

ToBeWritten之汽车信息安全威胁建模

也许每个人出生的时候都以为这世界都是为他一个人而存在的&#xff0c;当他发现自己错的时候&#xff0c;他便开始长大 少走了弯路&#xff0c;也就错过了风景&#xff0c;无论如何&#xff0c;感谢经历 转移发布平台通知&#xff1a;将不再在CSDN博客发布新文章&#xff0c;敬…

itop-3568开发板驱动学习笔记(9)高级字符设备(三)信号驱动 IO

《【北京迅为】itop-3568开发板驱动开发指南.pdf》 学习笔记 文章目录应用层信号机制应用层开启异步通知驱动层异步通知接口实验代码信号驱动 IO 不需要像 poll 一样查询设备的状态&#xff0c;一旦设备有目标事件发生&#xff0c;就会触发 SIGIO 信号&#xff0c;然后处理信号…

Eyeshot .NET 2023.1 Crack

概述 Eyeshot 是.NET 的 CAD 控件。它本身支持Windows Forms和Windows Presentation Foundation。它随附四个不同的Visual Studio工具箱项目&#xff1a;用于 2D 和 3D 几何创建或编辑的设计、用于自动生成 2D 视图的 绘图、使用线性静态分析进行几何验证的模拟以及用于CNC刀具…

MySQL学习笔记(十八)—— 事务基本知识

1. 数据库事务概述 存储引擎支持请况 SHOW ENGINES; # 命令来查看当前 MySQL 支持的存储引擎都有哪些&#xff0c;以及这些存储引擎是否支持事务。能看出在 MySQL 中&#xff0c;只有InnoDB 是支持事务的。 基本概念 事务&#xff1a;一组逻辑操作单元&#xff0c;使数据从一…

4.8 Beijing Rust Meetup | Call For Presenters

如果你有兴趣参与探讨Rust作为一种强调性能、安全和并发性的编程语言的各种应用、实践和无限可能性的头脑风暴&#xff0c;就一定不能错过这场来自达坦科技、南京大学、CloudWeGo、华为等技术专家带来的关于Rust编程语言相关应用的线下Meetup。我们的主题是Rust &#x1f4a1;X…