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

《剑指 Offer》专项突破版 - 面试题 70 : 排序数组中只出现一次的数字(C++ 实现)

题目链接:LCR 070. 有序数组中的单一元素 - 力扣(LeetCode)

题目

在一个排序的数组中,除一个数字只出现一次之外,其他数字都出现了两次,请找出这个唯一只出现一次的数字。例如,在数组 [1, 1, 2, 2, 3, 4, 4, 5, 5] 中,数字 3 只出现了一次。

分析

如果将题目的条件稍稍改动,输入的数组没有经过排序,其他条件不变,那么这就是另一类很经典的面试题。由于两个相同的数字异或的结果是 0,因此如果将数组中所有数字异或,最终的结果就是那个唯一只出现一次的数字。我们需要计算数组中所有数字的异或,如果数组的长度为 n,那么这种解法的时间复杂度是 O(n)。

现在题目增加了一个条件,输入的数组是排序的,前面基于异或的解法仍然有效。但是面试官增加一个条件,可能是希望应聘者能够想出新的更好的解法。既然是在排序数组中查找某个数字,就尝试应用二分查找算法。

由于只出现一次的数字的左边有偶数个数字,因此它的下标 x 一定是偶数(下标从 0 开始),可以在偶数下标范围内二分查找。二分查找的目标是找到第一个 nums[x] nums[x + 1] 的偶数下标

可以将数组中的数字每两个分成一组,最初的若干组的两个数字都是相同的。但遇到只出现一次的数字之后,情况发生变化。这个只出现一次的数字和后面的数字结合成一组,导致后面所有组的两个数字都不相同。由此可见,只出现一次的数字正好是第一个两个数字不相同的分组的第 1 个数字

初始化,二分查找的左边界是 0,右边界是数组的最大偶数下标,即数组的长度减 1(因为数组的长度是奇数)。每次取左右边界的平均值 mid 作为判断的下标,如果 mid 是奇数,则将 mid 减 1,确保 mid 是偶数,然后比较 nums[mid] 和 nums[mid + 1] 是否相等,如果相等,则 mid < x,调整左边界;否则 mid >= x,调整有边界。调整边界之后继续二分查找,直到确定下标 x 的值

代码实现

class Solution {
public:int singleNonDuplicate(vector<int>& nums) {int left = 0;int right = nums.size() - 1;while (left < right){int mid = (left + right) / 2;if (mid % 2 != 0)--mid;if (nums[mid] == nums[mid + 1])left = mid + 2;elseright = mid;}return nums[left];}
};

相关文章:

《剑指 Offer》专项突破版 - 面试题 70 : 排序数组中只出现一次的数字(C++ 实现)

题目链接&#xff1a;LCR 070. 有序数组中的单一元素 - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 在一个排序的数组中&#xff0c;除一个数字只出现一次之外&#xff0c;其他数字都出现了两次&#xff0c;请找出这个唯一只出现一次的数字。例如&#xff0c;在…...

Linux安全加固功能

提示:工具下载链接在文章最后 目录 一.加固功能介绍二.配置加固功能1.配置安全加固功能1.1 开放目前设备监听的所有端口1.2 只开放80、443、20、21、22端口1.3 防火墙配置工具1.3.1 开放允许访问的端口1.3.2 删除允许访问的端口1.3.3 添加IP地址允许访问规则1.3.4 添加IP地址禁…...

最新AI系统ChatGPT网站H5系统源码,支持Midjourney绘画

一、前言 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图文教程吧。已支持GPT…...

【服务器数据恢复】昆腾存储中raid5磁盘阵列数据恢复案例

服务器数据恢复环境&故障&#xff1a; 10个磁盘柜&#xff0c;每个磁盘柜配24块硬盘。9个磁盘柜用于存储数据&#xff0c;1个磁盘柜用于存储元数据。 元数据存储中24块硬盘&#xff0c;组建了9组RAID1阵列1组RAID10阵列&#xff0c;4个全局热备硬盘。 数据存储中&#xff0…...

企业微信变更主体怎么改?

企业微信变更主体有什么作用&#xff1f;现在很多公司都用企业微信来加客户&#xff0c;有时候辛辛苦苦积累了很多客户&#xff0c;但是公司却因为各种各样的原因需要注销&#xff0c;那么就需要通过企业微信变更主体的方法&#xff0c;把企业微信绑定的公司更改为最新的。企业…...

常用生理眼电信号整理合集 (EOG)

目录 Sleep-EDF Sleep-EDF expanded Sleep-EDF 这些信号是从白人男性和女性&#xff08;21-35 岁&#xff09;中获得的&#xff0c;没有任何药物治疗&#xff1b;它们包含水平 EOG、FpzCz 和 PzOz EEG&#xff0c;每个采样频率为 100 Hz。 sc* 记录还包含颏下肌电图包络、口鼻…...

【场景题】让你设计一个订单号生成服务,该怎么做?

方案 当设计订单号生成服务时&#xff0c;我们需要考虑唯一性、数据量、可读性、基因法、可扩展性、高性能和高可用性等多个方面。根据这些考虑&#xff0c;一个简单的订单号生成服务设计方案可以采取以下措施&#xff1a; 使用Snowflake算法或第三方分布式ID生成器&#xff…...

使用GraphView实现简单的绘图工具

ShapeItem代码&#xff1a; ShapeItem::ShapeItem(ShapeType type) {m_type type;m_lt QPointF(0, 0);m_rb QPointF(0, 0);m_deleteEnable false;m_bll BllData::getInstance();connect(m_bll, &BllData::deleteShapeEnableSignal, this, &ShapeItem::deleteShap…...

javaWebssh教师荣誉库管理系统myeclipse开发mysql数据库MVC模式java编程计算机网页设计

一、源码特点 java ssh在线授课辅导系统是一套完善的web设计系统&#xff08;系统采用ssh框架进行设计开发&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为TOMCAT7.0…...

Android minigbm框架普法

Android minigbm框架普法 引言 假设存在这么一个场景&#xff0c;我的GPU的上层实现走的不是标准的Mesa接口&#xff0c;且GPU也没有提专门配套的gralloc和hwcompoer实现。那么我们的Android要怎么使用到EGL和GLES库呢&#xff0c;并且此GPU驱动是支持drm实现的&#xff0c;也有…...

01、MongoDB -- 下载、安装、配置文件等配置 及 副本集配置

目录 MongoDB -- 下载、安装、配置 及 副本集配置启动命令启动 mongodb 的服务器&#xff08;单机和副本集&#xff09;启动单机模式的 mongodb 服务器启动副本集的 3 个副本节点&#xff08;mongodb 服务器&#xff09; 启动 mongodb 的客户端 MongoDB 下载MongoDB 安装1、解压…...

uniapp中导入css和scss的区别

在项目中编写了一个基础的公共样式 common.scss文件 想要将其 导入到app.vue文件中 第一次使用的是import url(static/common.scss); 编译直接报错&#xff0c;无法识别这个文件 原因是 使用import url()是CSS中用于导入外部样式表的语法&#xff0c;但它不适用于导入SCS…...

RabbitMQ-TTL/死信队列/延迟队列高级特性

文章目录 TTL死信队列消息成为死信的三种情况队列如何绑定死信交换机 延迟队列RabbitMQ如何实现延迟队列 总结来源B站黑马程序员 TTL TTLTTL(Time To Live):存活时间/过期时间当信息到达存活时间后&#xff0c;还没有被消费&#xff0c;会被自动清除。RabbitMQ可以对消息设置过…...

docker安装php7.4安装(swoole)

容器 docker pull centos:centos7 docker run -dit -p9100:9100 --name“dade” --privilegedtrue centos:centos7 /usr/sbin/init 一、安装前库文件和工具准备 1、首先安装 EPEL 源 yum -y install epel-release2.安装 REMI 源 yum -y install http://rpms.remirepo.net/en…...

身份证识别系统(安卓)

设计内容与要求&#xff1a; 通过手机摄像头捕获身份证信息&#xff0c;将身份证上的姓名、性别、出生年月、身份证号码保存在数据库中。1&#xff09;所开发Apps软件至少需由3-5个以上功能性界面组成。要求&#xff1a;界面美观整洁、方便应用&#xff1b;可以使用Android原生…...

Python教程——最后一波来喽

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 1.使用__slots__2. property3.多重继承 4.定制类5.枚举类6.错误处理7.调试8. 文档测试9.单元测试10. 文件读写11. StringIO和BytesIO12. 操作文件和目录13.序列化14…...

学生管理系统(python实现)

新增学生显示学生查找学生删除学生存档到文件 约定好数据的存储格式&#xff1a; 约定把数据保存在和py文件同级目录中&#xff0c;文件名为record.txt 文件内容按照行文本的方式来表示 首先这是一个文本文件&#xff0c;里面包含了很多行&#xff0c;每一行代表一个学生 …...

Java读取文件

读取文件为String 、访问链接直接跳转html 环境&#xff1a;SpringMVC 、前端jsp InputStreamReader FileInputStream fileInputStream new FileInputStream(formatFile.getHtmlpath());InputStreamReader reader new InputStreamReader(fileInputStream, StandardCharsets…...

曾桂华:车载座舱音频体验探究与思考| 演讲嘉宾公布

智能车载音频 I 分论坛将于3月27日同期举办&#xff01; 我们正站在一个前所未有的科技革新的交汇点上&#xff0c;重塑我们出行体验的变革正在悄然发生。当人工智能的磅礴力量与车载音频相交融&#xff0c;智慧、便捷与未来的探索之旅正式扬帆起航。 在驾驶的旅途中&#xff0…...

面试题HTML+CSS+网络+浏览器篇

文章目录 Css预处理sass less是什么&#xff1f;为什么使用他们怎么转换 less 为 css&#xff1f;重绘和回流是什么http 是什么&#xff1f;有什么特点HTTP 协议和 HTTPS 区别什么是 CSRF 攻击HTML5 新增的内容有哪些Css3 新增的特性flex VS grid清除浮动的方式有哪些&#xff…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践

01技术背景与业务挑战 某短视频点播企业深耕国内用户市场&#xff0c;但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大&#xff0c;传统架构已较难满足当前企业发展的需求&#xff0c;企业面临着三重挑战&#xff1a; ① 业务&#xff1a;国内用户访问海外服…...