(位运算) 剑指 Offer 56 - I. 数组中数字出现的次数 ——【Leetcode每日一题】

news/2024/2/27 19:49:54

❓剑指 Offer 56 - I. 数组中数字出现的次数

难度:中等

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O ( n ) O(n) O(n),空间复杂度是 O ( 1 ) O(1) O(1)

示例 1:

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]

示例 2:

输入:nums = [1,2,10,4,1,4,3,3]
输出:[2,10] 或 [10,2]

限制

  • 2 <= nums.length <= 10000

💡思路:位运算

基础知识必知:一篇文章搞懂位运算!!!

两个相等的元素 异或 的结果为 0,而 0 与任意数 x 异或 的结果都为 x

对本题给的数组的所有元素执行异或操作,得到的是两个不存在重复的元素异或的结果。例如对于数组 [x,x,y,y,z,k]x^x^y^y^z^k = 0^y^y^z^k = y^y^z^k = 0^z^k = z^k

两个不相等的元素在位级表示上一定会有所不同,因此这两个元素异或得到的结果 diff 一定不为 0:

  • 使用 ans[0] = diff 先保存这两个数的结果;
  • 位运算 diff & -diff 能得到 diff 位级表示中 最右侧为 1 的位,令 diff = diff & -diff
  • diff 作为区分两个元素的依据,一定有一个元素对 diff 进行 运算的结果为 diff ,另一个结果为 0。

设不相等的两个元素分别为 xy,遍历数组所有元素,判断每一个元素与 diff 结果是否为 diff :

  • 如果是的话将元素与 x 进行 异或 并赋值给 ans[1]
  • 数组中相等的元素一定会同时与 x 异或操作,而且这些相等的元素异或的结果为 0,因此最后 只剩下 x 与 0 异或的结果;
  • 另一个元素 y = ans[0] ^ x

🍁代码:(C++、Java)

C++

class Solution {
public:vector<int> singleNumbers(vector<int>& nums) {vector<int> ans(2);int diff = 0;for(int num : nums){//得到只出现一次的两个数的异或diff ^= num;}ans[0] = diff; //记录两个数的异或结果diff &= -diff; //得到最后一位1for(int num : nums){//得到其中一个数if((num & diff) == diff){ans[1] ^= num; }}ans[0] ^= ans[1];//得到另一个数return ans;}
};

Java

class Solution {public int[] singleNumbers(int[] nums) {int[] ans = new int[2];int diff = 0;for(int num : nums){//得到只出现一次的两个数的异或diff ^= num;}ans[0] = diff; //记录两个数的异或结果diff &= -diff; //得到最后一位1for(int num : nums){//得到其中一个数if((num & diff) == diff){ans[1] ^= num; }}ans[0] ^= ans[1];//得到另一个数return ans;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),我们只需要遍历数组两次。
  • 空间复杂度 O ( 1 ) O(1) O(1),只需要常数的空间存放若干变量。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/1084899.html

相关文章

Linux 云服务器挂载数据盘

1、检查linux服务器磁盘情况 df -h 可以看到无磁盘挂载信息。 2、查看待挂载磁盘信息 fdisk -l 可以看到40G系统盘、50G数据盘&#xff08;盘符&#xff1a;/dev/vdb&#xff09; 3、对数据盘分区 fdisk /dev/vdb 根据提示&#xff0c;依次输入“n”&#xff0c;“p”“1…

【Apollo学习笔记】——规划模块TASK之PATH_ASSESSMENT_DECIDER

文章目录 前言PATH_ASSESSMENT_DECIDER功能简介PATH_ASSESSMENT_DECIDER相关信息PATH_ASSESSMENT_DECIDER总体流程1. 去除无效路径2. 分析并加入重要信息给speed决策SetPathInfoSetPathPointType 3. 排序选择最优的路径4. 更新必要的信息 前言 在Apollo星火计划学习笔记——Ap…

矢量图片转换 Vector Magic for mac

Vector Magic会帮你进行自动识别和分析&#xff0c;转换过程中用户可选择相应的转换级别&#xff0c;从而达到自已所需的效果。 只需上传即可在线自动将 JPG、PNG、BMP 和 GIF 位图图像转换为真正的 SVG、Eps 和 PDF 矢量图像。真正的全彩描摹&#xff0c;无需安装软件&#xf…

语言基础篇7——Python运算符

运算符 算数运算符 # 算术运算符 # # - # * # ** # / 浮点除 # // 整数除 # %赋值运算符 # 赋值运算符 # # # - # / 浮点除等 # // 整数除等 # * # **关系运算符 # 关系运算符 # > # # < # > # < # ! # is # is not逻辑运算符 # 逻辑运算符 # 返回表达式…

查漏补缺 - JS之一

目录 1&#xff0c;程序流程控制2&#xff0c;变量&#xff0c;字面量&#xff0c;表达式3&#xff0c;函数4&#xff0c;数据的存储和传递5&#xff0c;函数作用域6&#xff0c;全局对象7&#xff0c;构造函数&#xff0c;原型&#xff0c;this&#xff0c;原型链&#xff0c;…

华为OD:敏感字段加密

题目描述&#xff1a; 给定一个由多个命令字组成的命令字符串&#xff1a; 1、字符串长度小于等于127字节,只包含大小写字母,数字,下划线和偶数个双引号&#xff1b; 2、命令字之间以一个或多个下划线_进行分割&#xff1b; 3、可以通过两个双引号”"来标识包含下划线…

python中list的两个无返回值函数

list是python中一个比较常用的数据结构&#xff0c;相当于其它语言的数据&#xff0c;list有很多方法&#xff0c;但是有的方法有返回值&#xff0c;有的没有返回值&#xff0c;因为多数情况下我调用函数的时候&#xff0c;习惯的认为函数会有返回值&#xff0c;但是如果突然出…

硅谷课堂3

文章目录 一、微信授权登录1、需求描述2、授权登录2.1、配置授权回调域名2.2、前端处理3、授权登录接口3.1、引入微信工具包3.2、添加配置3.3、添加工具类3.4、controller类3.5、编写`getByOpenid(String openId)`方法3.6、编写`JwtHelper.createToken()`方法3.6.1、JWT介绍3.6…

互联网摸鱼日报(2023-09-01)

互联网摸鱼日报(2023-09-01) 36氪新闻 暑期剧综营销复盘&#xff1a;要么小单快返&#xff0c;要么长线绑定 ESG管理商「Wint」融资3500万美元、WeWork启动债务重组、北京规划机器人产业园&#xff5c;PropTech周刊73期 小米应用商店关闭红包专场&#xff0c;羊毛党遭遇痛击…

Linux 调试技术 Kprobe

目录 用途&#xff1a;一、技术背景1.1 kprobes的特点与使用限制1.2 kprobe原理 二、 基于kprobe探测模块的探测方式2.1、struct kprobe结构体2.2 kprobe API函数2.3 示例代码参考资料&#xff1a; 用途&#xff1a; 判断内核函数是否被调用&#xff0c;获取调用上下文、入参以…

【AI】数学基础——信息论

不确定性才是客观世界的本质属性。不确定性的世界只能使用概率模型来描述&#xff0c;正是对概率模型的刻画促成了信息论的的诞生 香农——通信的数学理论&#xff0c;给定了对信息这一定性概念的定量分析方法 信息论在世界的不确定性和消息的可测量性之间搭建桥梁 条件熵和…

【Rust】003-基础语法:流程控制

【Rust】003-基础语法&#xff1a;流程控制 文章目录 【Rust】003-基础语法&#xff1a;流程控制一、概述二、if 表达式1、语法格式2、多个3、获取表达式的值 三、循环1、loop&#xff1a;无限循环&#xff0c;可跳出无限循环跳出循环返回值 2、while&#xff1a;条件循环&…

flutter plugins插件【二】【FlutterAssetsGenerator】

2、FlutterAssetsGenerator 介绍地址&#xff1a;https://juejin.cn/post/6898542896274735117 配置assets目录 ​ 插件会从pubspec.yaml文件下读取assets目录&#xff0c;因此要使用本插件&#xff0c;你需要在pubspec.yaml下配置资源目录 flutter:# The following line ens…

Sharding-JDBC分片策略

Sharding-JDBC分片策略 包含分片键和分片算法&#xff0c;由于分片算法的独立性&#xff0c;将其独立抽离。真正可用于分片操作的是分片键 分片算法&#xff0c;也就是分片策略。目前提供5种分片策略。 一个好的分片策略好的分片键好的的分片算法 1. 标准分片策略 对应Stan…

【VTK】 vtkMapper

很高兴在雪易的CSDN遇见你 ,给你糖糖 欢迎大家加入雪易社区-CSDN社区云 前言 本文主要分享VTK中关于vtkMapper的相关知识和使用方法,希望对各位小伙伴有所帮助! 感谢各位小伙伴的点赞+关注,小易会继续努力分享,一起进步! 你的点赞就是我的动力(^U^)ノ~YO </

kakfa 3.5 kafka服务端处理消费者客户端拉取数据请求源码

一、服务端接收消费者拉取数据的方法二、遍历请求中需要拉取数据的主题分区集合&#xff0c;分别执行查询数据操作&#xff0c;1、需要选择适合的主题副本进行数据的读取操作&#xff0c;这里选项列表中需要排除分区Leader副本 三、区分是Follower拉取数据还是消费者拉取数据请…

【微服务部署】三、Jenkins+Maven插件Jib一键打包部署SpringBoot应用Docker镜像步骤详解

前面我们介绍了K8SDockerMaven插件打包部署SpringCloud微服务项目&#xff0c;在实际应用过程中&#xff0c;很多项目没有用到K8S和微服务&#xff0c;但是用到了Docker和SpringBoot&#xff0c;所以&#xff0c;我们这边介绍&#xff0c;如果使用Jenkinsjib-maven-plugin插件打…

博客程序系统其它功能扩充

一、注册功能 1、约定前后端接口 2、后端代码编写 WebServlet("/register") public class RegisterServlet extends HttpServlet {Overrideprotected void doPost(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {//设置…

选择 Guava EventBus 还是 Spring Framework ApplicationEvent

文章首发地址 Spring Framework ApplicationEvent Spring Framework 的 ApplicationEvent 是 Spring 框架提供的一种事件机制&#xff0c;用于实现发布和订阅事件的功能。它基于观察者模式&#xff0c;允许应用程序内的组件之间进行松耦合的通信。 下面是关于 Spring Frame…

QT 设置应用程序图标

1.下载xx.ico图标&#xff1a;ico网址 2.在线PNG转换ICO&#xff1a;png在线转换ico 3.添加图标资源 1&#xff09;新建文件路径 2&#xff09;添加图片资源 3&#xff09;在 .pro文件里面添加图片 4&#xff09;将xx.ico放到工程目录&#xff0c;编译完可以看到xx.exe的图标…
最新文章