【位运算】leetcode面试题:消失的两个数字
一.题目描述
消失的两个数字

二.思路分析
本题难度标签是困难,但实际上有了只出现一次的数字iii这道题的铺垫,本题的思路还是很容易想到的。
温馨提示:阅读本文前可以先查看我的【位运算】专栏的第一篇文章,其中包含位运算这类题型的常用技巧以及前面这道题的讲解。
言归正传,这道题最容易想到的解法应该是哈希表,遍历数组,用哈希表记录每个元素出现的次数。然后再遍历哈希表,出现次数为0的元素就是我们要找的答案。但是空间复杂度为O(n),不符合题目要求。
下面介绍位运算的方法:
若数组的长度为n,则数组缺少了[1, n+2]中的两个数。
先将从1到n+2的所有整数异或在一起,然后再异或数组的每个元素。异或的特点是“消消乐”,即两个相同的数异或会变成0,故最终的结果tmp相当于这两个缺失的数异或。
这两个数既然不同,那么它们至少有一个比特位不一样,我们可以遍历tmp的每一个比特位,如果它是1,则说明两个数的这一位不相同(异或的规则是相异为1),记录这一位置。
随后我们根据这一比特位的不同,将[1,n+2]的整数以及数组的所有元素划分为两组,分别进行异或,相同的元素会消去,最终得到的就是我们要找的两个数。
三.代码实现
class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int n = nums.size();int tmp = 0;//将所有数异或在一起for (int i = 1; i <= n + 2; i++){tmp ^= i;}for (auto e : nums){tmp ^= e;}//找出缺失的两个数字哪一比特位不相同int pos = 0;for (int i = 0; i <= 31; i++){if (((tmp >> i) & 1) == 1){pos = i;break;}}//根据这一比特位不同,划分为两组分别异或int ret1 = 0, ret2 = 0;for (int i = 1; i <= n + 2; i++){if (((i >> pos) & 1) == 1){ret1 ^= i;}else{ret2 ^= i;}}for (auto e : nums){if (((e >> pos) & 1) == 1){ret1 ^= e;}else{ret2 ^= e;}}return {ret1, ret2};}
};
欢迎进入我的主页,翻阅算法专栏,学习更多有趣的算法。
相关文章:
【位运算】leetcode面试题:消失的两个数字
一.题目描述 消失的两个数字 二.思路分析 本题难度标签是困难,但实际上有了只出现一次的数字iii这道题的铺垫,本题的思路还是很容易想到的。 温馨提示:阅读本文前可以先查看我的【位运算】专栏的第一篇文章,其中包含位运算这类…...
Vue2 集成 CodeMirror 实现公式编辑、块状文本编辑,TAG标签功能
效果图 安装codemirror依赖 本示例为Vue2项目,安装低版本的依赖 npm i codemirror5.65.12 npm i vue-codemirror4.0.6 实现 实现代码如下,里边涉及到的变量和函数自行替换即可,没有其他复杂逻辑。 <template><div class"p…...
CCF-CSP 30次 第二题【矩阵运算】
计算机软件能力认证考试系统 #include<bits/stdc.h> using namespace std; const int N1e410; #define int long long int n,d; int q[N][22],k[22][N],v[N][22],w[N]; int ans1[N][22],ans2[N][22]; signed main() {scanf("%lld %lld",&n,&d);for(in…...
最大子数组和【贪心算法】
最大子数组和 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 class Solution {public int maxSubArray(int[] nums) {//记录最大结果&…...
linux并发服务器 —— Makefile与GDB调试(二)
Makefile Makefile:定义规则指定文件的编译顺序;类似shell脚本,执行操作系统命令 优点:自动化编译——通过make(解释Makefile文件中指令的命令)命令完全编译整个工程,提高软件开发效率&#x…...
Ansible学习笔记14
实现多台的分离实现: [rootlocalhost playbook]# cat example3.yaml --- - hosts: 192.168.17.105remote_user: roottasks:- name: create test1 directoryfile: path/test1/ statedirectory- hosts: 192.168.17.106remote_user: roottasks:- name: create test2 d…...
docker 安装 mysql 并挂载 配置文件和数据目录
1、宿主机创建挂载目录 sudo mkdir /path/mysql/data sudo mkdir /path/mysql/conf2、搜索镜像 docker search mysql拉取官方支持版本(OFFICIAL 为 ok的版本) docker pull mysql:latest3、以 mysql 作为基础镜像构建容器并挂载目录 docker run -d -p…...
代码随想录训练营 DP01
代码随想录训练营 DP01 509. 🌸斐波那契数🌸code 70. 🌸爬楼梯🌸code 746. 🌸使用最小花费爬楼梯🌸code 509. 🌸斐波那契数🌸 斐波那契数 (通常用 F(n) 表示)…...
github+hexo 博客搭建
文章目录 1.安装Node.js、Git和Hexo2.创建 GitHub 仓库并配置ssh3.初始化Hexo4.配置Hexo5.创建博客内容6.部署7.查看8.参考:9.选择主题: 环境:win11wsl 1.安装Node.js、Git和Hexo 打开终端安装以下软件 sudo apt update sudo apt-get insta…...
Spring Security bug记录:antMatchers找不到符号(已解决)
目录 Spring Security bug记录:antMatchers找不到符号(已解决)原因:解决:参考链接: Spring Security bug记录:antMatchers找不到符号(已解决) 原因: 新版本…...
kaggle新赛:谷歌AI模型运行时间预测赛题解析【数据挖掘】
赛题名称:Google - Fast or Slow? Predict AI Model Runtime 赛题链接:https://www.kaggle.com/competitions/predict-ai-model-runtime 赛题背景 Alice 是一名 AI 模型开发人员,但她的团队开发的一些模型运行速度非常慢。她最近发现了编…...
mysql性能测试工具选择 mysql软件测试
1.理论知识: 1.1 定义 1. 基准测试是一种测量和评估软件性能指标的活动,用于建立某个时刻的性能基准,以便当系统发生软硬件变化时重新进行基准测试以评估变化对性能的影响 2. 基准测试是针对系统设置的一种压力测试,但是和压力测试还是有区…...
GPS全球卫星定位系统原理
GPS全球卫星定位系统是一种利用导航卫星进行定位、导航和时间测量的系统。它由三部分组成:空间部分、地面控制部分和用户设备部分。其中,空间部分由24颗卫星组成,分布在6个轨道面上,每个轨道面有4颗卫星;地面控制部分由…...
Ubuntu学习---跟着绍发学linux课程记录(第一部分)
文章目录 1、启动、关闭、挂起、恢复(电源)2、更多虚拟机操作2.1 电源设置2.2 硬件参数设置2.3 状态栏2.4 全屏显示 3、快照与系统恢复4、桌面环境5、文件系统6、用户目录7、创建目录和文件8、命令行:文件列表ls 9、命令行:切换目…...
Ubuntu20.04下安装google输入法
Ubuntu20.04下安装google输入法 1、添加中文语言支持 打开 系统设置——区域和语言——管理已安装的语言——在“语言”tab下——点击“添加或删除语言” 弹出“已安装语言”窗口,勾选中文(简体),点击应用 回到“语言支持”窗…...
Ros noetic 机器人坐标记录运动路径和发布 实战教程(A)
前言: 网上记录Path的写入文件看了一下还挺多的,有用yaml作为载体文件,也有用csv文件的路径信息,也有用txt来记录当前生成的路径信息,载体不重要,反正都是记录的方式,本文主要按yaml的方式写入,后文中将补全其余两种方式。 其中两种方式的主要区别在于,加载yaml所需要…...
Java“牵手”1688淘口令转换API接口数据,1688API接口申请指南
1688平台商品淘口令接口是开放平台提供的一种API接口,通过调用API接口,开发者可以获取1688商品的标题、价格、库存、商品快递费用,宝贝ID,发货地,区域ID,快递费用,月销量、总销量、库存、详情描…...
Python实现自动关键词提取
随着互联网的发展,越来越多的人喜欢在网络上阅读小说。本文将通过详细示例,向您介绍如何使用Python编写爬虫程序来获取网络小说,并利用自然语言处理技术实现自动文摘和关键词提取功能。 1. 网络小说数据抓取 首先,请确保已安装必…...
java八股文面试[多线程]——sleep wait join yield
sleep和wait有什么区别 sleep 方法和 wait 方法都是用来将线程进入阻塞状态的,并且 sleep 和 wait 方法都可以响应 interrupt 中断,也就是线程在休眠的过程中,如果收到中断信号,都可以进行响应并中断,且都可以抛出 In…...
Vue/React 项目部署到服务器后,刷新页面出现404报错
问题描述:在本地启动项目一切正常,部署到服务器上线后出现BUG,项目刷新页面出现404。 起初以为是自己路由守卫或是token丢失问题,找了一圈终于解决了 产生原因:我们打开vue/react打包后生成的dist文件夹,可…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
Canal环境搭建并实现和ES数据同步
作者:田超凡 日期:2025年6月7日 Canal安装,启动端口11111、8082: 安装canal-deployer服务端: https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...
SQL注入篇-sqlmap的配置和使用
在之前的皮卡丘靶场第五期SQL注入的内容中我们谈到了sqlmap,但是由于很多朋友看不了解命令行格式,所以是纯手动获取数据库信息的 接下来我们就用sqlmap来进行皮卡丘靶场的sql注入学习,链接:https://wwhc.lanzoue.com/ifJY32ybh6vc…...
