当前位置: 首页 > news >正文

【位运算】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面试题:消失的两个数字

一.题目描述 消失的两个数字 二.思路分析 本题难度标签是困难&#xff0c;但实际上有了只出现一次的数字iii这道题的铺垫&#xff0c;本题的思路还是很容易想到的。 温馨提示&#xff1a;阅读本文前可以先查看我的【位运算】专栏的第一篇文章&#xff0c;其中包含位运算这类…...

Vue2 集成 CodeMirror 实现公式编辑、块状文本编辑,TAG标签功能

效果图 安装codemirror依赖 本示例为Vue2项目&#xff0c;安装低版本的依赖 npm i codemirror5.65.12 npm i vue-codemirror4.0.6 实现 实现代码如下&#xff0c;里边涉及到的变量和函数自行替换即可&#xff0c;没有其他复杂逻辑。 <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 &#xff0c;请你找出一个具有最大和的连续子数组&#xff08;子数组最少包含一个元素&#xff09;&#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。 class Solution {public int maxSubArray(int[] nums) {//记录最大结果&…...

linux并发服务器 —— Makefile与GDB调试(二)

Makefile Makefile&#xff1a;定义规则指定文件的编译顺序&#xff1b;类似shell脚本&#xff0c;执行操作系统命令 优点&#xff1a;自动化编译——通过make&#xff08;解释Makefile文件中指令的命令&#xff09;命令完全编译整个工程&#xff0c;提高软件开发效率&#x…...

Ansible学习笔记14

实现多台的分离实现&#xff1a; [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拉取官方支持版本&#xff08;OFFICIAL 为 ok的版本&#xff09; docker pull mysql:latest3、以 mysql 作为基础镜像构建容器并挂载目录 docker run -d -p…...

代码随想录训练营 DP01

代码随想录训练营 DP01 509. &#x1f338;斐波那契数&#x1f338;code 70. &#x1f338;爬楼梯&#x1f338;code 746. &#x1f338;使用最小花费爬楼梯&#x1f338;code 509. &#x1f338;斐波那契数&#x1f338; 斐波那契数 &#xff08;通常用 F(n) 表示&#xff09;…...

github+hexo 博客搭建

文章目录 1.安装Node.js、Git和Hexo2.创建 GitHub 仓库并配置ssh3.初始化Hexo4.配置Hexo5.创建博客内容6.部署7.查看8.参考&#xff1a;9.选择主题&#xff1a; 环境&#xff1a;win11wsl 1.安装Node.js、Git和Hexo 打开终端安装以下软件 sudo apt update sudo apt-get insta…...

Spring Security bug记录:antMatchers找不到符号(已解决)

目录 Spring Security bug记录&#xff1a;antMatchers找不到符号&#xff08;已解决&#xff09;原因&#xff1a;解决&#xff1a;参考链接&#xff1a; Spring Security bug记录&#xff1a;antMatchers找不到符号&#xff08;已解决&#xff09; 原因&#xff1a; 新版本…...

kaggle新赛:谷歌AI模型运行时间预测赛题解析【数据挖掘】

赛题名称&#xff1a;Google - Fast or Slow? Predict AI Model Runtime 赛题链接&#xff1a;https://www.kaggle.com/competitions/predict-ai-model-runtime 赛题背景 Alice 是一名 AI 模型开发人员&#xff0c;但她的团队开发的一些模型运行速度非常慢。她最近发现了编…...

mysql性能测试工具选择 mysql软件测试

1.理论知识: 1.1 定义 1. 基准测试是一种测量和评估软件性能指标的活动&#xff0c;用于建立某个时刻的性能基准&#xff0c;以便当系统发生软硬件变化时重新进行基准测试以评估变化对性能的影响 2. 基准测试是针对系统设置的一种压力测试&#xff0c;但是和压力测试还是有区…...

GPS全球卫星定位系统原理

GPS全球卫星定位系统是一种利用导航卫星进行定位、导航和时间测量的系统。它由三部分组成&#xff1a;空间部分、地面控制部分和用户设备部分。其中&#xff0c;空间部分由24颗卫星组成&#xff0c;分布在6个轨道面上&#xff0c;每个轨道面有4颗卫星&#xff1b;地面控制部分由…...

Ubuntu学习---跟着绍发学linux课程记录(第一部分)

文章目录 1、启动、关闭、挂起、恢复&#xff08;电源&#xff09;2、更多虚拟机操作2.1 电源设置2.2 硬件参数设置2.3 状态栏2.4 全屏显示 3、快照与系统恢复4、桌面环境5、文件系统6、用户目录7、创建目录和文件8、命令行&#xff1a;文件列表ls 9、命令行&#xff1a;切换目…...

Ubuntu20.04下安装google输入法

Ubuntu20.04下安装google输入法 1、添加中文语言支持 打开 系统设置——区域和语言——管理已安装的语言——在“语言”tab下——点击“添加或删除语言” 弹出“已安装语言”窗口&#xff0c;勾选中文&#xff08;简体&#xff09;&#xff0c;点击应用 回到“语言支持”窗…...

Ros noetic 机器人坐标记录运动路径和发布 实战教程(A)

前言: 网上记录Path的写入文件看了一下还挺多的,有用yaml作为载体文件,也有用csv文件的路径信息,也有用txt来记录当前生成的路径信息,载体不重要,反正都是记录的方式,本文主要按yaml的方式写入,后文中将补全其余两种方式。 其中两种方式的主要区别在于,加载yaml所需要…...

Java“牵手”1688淘口令转换API接口数据,1688API接口申请指南

1688平台商品淘口令接口是开放平台提供的一种API接口&#xff0c;通过调用API接口&#xff0c;开发者可以获取1688商品的标题、价格、库存、商品快递费用&#xff0c;宝贝ID&#xff0c;发货地&#xff0c;区域ID&#xff0c;快递费用&#xff0c;月销量、总销量、库存、详情描…...

Python实现自动关键词提取

随着互联网的发展&#xff0c;越来越多的人喜欢在网络上阅读小说。本文将通过详细示例&#xff0c;向您介绍如何使用Python编写爬虫程序来获取网络小说&#xff0c;并利用自然语言处理技术实现自动文摘和关键词提取功能。 1. 网络小说数据抓取 首先&#xff0c;请确保已安装必…...

java八股文面试[多线程]——sleep wait join yield

sleep和wait有什么区别 sleep 方法和 wait 方法都是用来将线程进入阻塞状态的&#xff0c;并且 sleep 和 wait 方法都可以响应 interrupt 中断&#xff0c;也就是线程在休眠的过程中&#xff0c;如果收到中断信号&#xff0c;都可以进行响应并中断&#xff0c;且都可以抛出 In…...

Vue/React 项目部署到服务器后,刷新页面出现404报错

问题描述&#xff1a;在本地启动项目一切正常&#xff0c;部署到服务器上线后出现BUG&#xff0c;项目刷新页面出现404。 起初以为是自己路由守卫或是token丢失问题&#xff0c;找了一圈终于解决了 产生原因&#xff1a;我们打开vue/react打包后生成的dist文件夹&#xff0c;可…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...

el-amap-bezier-curve运用及线弧度设置

文章目录 简介示例线弧度属性主要弧度相关属性其他相关样式属性完整示例链接简介 ‌el-amap-bezier-curve 是 Vue-Amap 组件库中的一个组件,用于在 高德地图 上绘制贝塞尔曲线。‌ 基本用法属性path定义曲线的路径,可以是多个弧线段的组合。stroke-weight线条的宽度。stroke…...