[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);//异或结果二进制中最低位的1
        int ret1 = 0;
        int ret2 = 0;
        for(auto e:nums)
        {
            if(e&j)//在作为区分的二进制上数值为1
            {
                ret1^=e;
            }
            else在作为区分的二进制上数值为0
            {
                ret2^=e;
            }
        }
        return {ret1,ret2};
    }
};

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

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

相关文章

Tiktok矩阵系统是什么?——Tiktok矩阵系统的优势、功能、及应用场景的介绍

摘要 Tiktok作为全球现象级的短视频平台,其发展前景日益明朗。 Tiktok全世界有多少用户? TikTok作为全球性的社交媒体平台,其用户数量一直在持续增长。根据最新的数据,预计到2024年,TikTok的用户数量将达到数十亿,覆盖全球范围内的各个年龄段和地区。具体来说,根据Ti…

总结SQL相对常用的几个字符函数

目录 字符的截取 substr() trim()、ltrim()、rtrim() 字符串的拼接 ||、 字符的大小写转换 upper(column_name):大写 lower(column_name):小写 字符替换 replace() 搜索字符 instr(column_name, substring_to_find,start,n_appearence) charindex(substring_to_fi…

HarmonyOS4.0 ArkUI构建布局

一、线性布局 属性说明&#xff1a; justifyContent&#xff1a;设置子元素在主轴方向的对齐方式 参数&#xff1a;FlexAlign枚举 alignItems&#xff1a;设置子元素在交叉轴方向的对齐方式 参数&#xff1a; Row容器使用VerticalAlign枚举Column容器使用HorizontalAlign枚举 …

k8s的ca以及相关证书签发流程

k8s的ca以及相关证书签发流程 1. kube-apiserver相关证书说明2. 生成CA凭证1.1. 生成CA私钥1.2. 生成CA证书 2. 生成kube-apiserver凭证2.1. 生成kube-apiserver私钥2.2. 生成kube-apiserver证书请求2.3. 生成kube-apiserver证书 3. 疑问和思考4. 参考文档 对于网站类的应用&am…

springboot 整合 mybatis(配置版)

代码及配置整合 创建实体类,与数据库对应 创建 mapper、service 和 controller @AutowiredUserService userService;@ResponseBody@GetMapping("/user")public com.vazquez.bootstudy.model.User getById(@RequestParam("id") Long id) {return userServ…

计算机网络:数据链路层 - CSMA/CD协议

计算机网络&#xff1a;数据链路层 - CSMA/CD协议 媒体接入控制CSMA/CD协议截断二进制指数退避算法帧长与帧间间隔信道利用率 媒体接入控制 如图所示&#xff0c;这是一根同轴电缆&#xff0c;有多台主机连接到这根同轴电缆上&#xff0c;他们共享这根传输媒体&#xff0c;形成…

LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆(优先队列)】

LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆&#xff08;优先队列&#xff09;】 题目描述&#xff1a;解题思路一&#xff1a;哈希表记录出现次数&#xff0c;然后用最小堆取&#xff0c;因为每次都是弹出最小的&#xff0c;剩下的一定是K…

CentOS7安装MySQL8.0教程

环境介绍 操作系统&#xff1a;Centos7.6 MySQL版本&#xff1a; 8.0.27 只要是8.0.*版本&#xff0c;那就可以按照本文说明安装 一、安装前准备 1、卸载MariaDB 安装MySQL的话会和MariaDB的文件冲突&#xff0c;所以需要先卸载掉MariaDB。 1.1、查看是否安装mariadb rpm -…

SQL注入利用学习-Union联合注入

联合注入的原理 在SQL语句中查询数据时&#xff0c;使用select 相关语句与where 条件子句筛选符合条件的记录。 select * from person where id 1; #在person表中&#xff0c;筛选出id1的记录如果该id1 中的1 是用户可以控制输入的部分时&#xff0c;就有可能存在SQL注入漏洞…

自媒体内容创作助手:7款必备ai写作工具一览! #学习方法#科技#其他

这些工具不仅可以快速生成高质量的文本内容&#xff0c;还可以根据用户的需求进行个性化定制。它们可以帮助我们节省大量的时间和精力&#xff0c;让我们更加专注于创意和细节的打磨。本文将为大家详细介绍几个AI写作工具&#xff0c;让你在写作领域更上一层楼。 1.七燕写作 这…

【随笔】Git 高级篇 -- 撤销变更 reset | revert(十四)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…

uniapp项目问题及解决(前后端互联)

1.路由跳转的问题 uni.navigateTo&#xff08;&#xff09; 保留当前页面&#xff0c;跳转到应用内的某个页面&#xff0c;使用uni.navigateBack可以返回到原页面 uni.redirectTo&#xff08;&#xff09; 关闭当前页面&#xff0c;跳转到应用内的某个页面。 uni.reLaunch&…

探索未来产业:新技术、新商业、新趋势

引言 随着科技的迅速发展和全球经济的不断变化&#xff0c;未来产业已经成为全球关注的焦点之一。未来产业的兴起不仅代表着新的商业机遇&#xff0c;更是对传统产业模式的颠覆和重构。在这个充满挑战和机遇的时代&#xff0c;我们不得不认真思考未来产业的重要性和前景。 未…

STM32之HAL开发——FatFs文件系统移植

FatFs文件系统移植 FatFs 程序结构图 移植 FatFs 之前我们先通过 FatFs 的程序结构图了解 FatFs 在程序中的关系网络 用户应用程序需要由用户编写&#xff0c;想实现什么功能就编写什么的程序&#xff0c;一般我们只用到 f_mount()、f_open()、 f_write()、f_read() 就可以…

在【Cencos7】中安装【Nacos】并适配【PostgreSQL】数据库

在【Cencos7】中安装【Nacos-2.3.0】并适配【PostgreSQL】数据库 安装JDK wget命令下载&#xff1a; wget https://repo.huaweicloud.com/java/jdk/8u151-b12/jdk-8u151-linux-x64.tar.gz解压 tar -xzvf jdk-7u80-linux-x64.tar.gz将解压后的目录移动到/opt下 sudo mv jdk…

unity_Button:单击的三种实现方式

1.针对特定单个按钮 此代码直接绑定到button上面无需其他操作 using UnityEngine; using UnityEngine.UI;public class PrintHelloOnButtonClick : MonoBehaviour {private Button button;void Start(){// 获取当前GameObject上的Button组件button GetComponent<Button&g…

【Redis系列】Spring Boot 集成 Redis 实现缓存功能

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

[C语言]——动态内存管理

目录 一.为什么要有动态内存分配 二.malloc和free 1.malloc 2.free 三.calloc和realloc 1.calloc 2.realloc 3.空间的释放​编辑 四.常见的动态内存的错误 1.对NULL指针的解引用操作 2.对动态开辟空间的越界访问 3.对非动态开辟内存使用free释放 4.使用free释放⼀块…

嘉轩智能工业科技诚邀您参观2024第13届生物发酵展

参展企业介绍 自2005年成立以来&#xff0c;嘉轩一直致力于工业智能永磁滚筒的研发、制造及销售&#xff0c;具有十多年的从业经验&#xff0c;公司主营产品包括工业智能永磁滚筒、机电智能诊断、工业智能电机等&#xff0c;高效智能自驱动永磁滚筒为我公司目前主导产品&#x…

【C++】——list的介绍及使用 模拟实现

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 文章目录 前言 一、list的介绍及使用 1.1 list的介绍 1.2 list的使用 1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity 1.2.4 list element access 1.…