《剑指 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++ 实现)
题目链接:LCR 070. 有序数组中的单一元素 - 力扣(LeetCode) 题目: 在一个排序的数组中,除一个数字只出现一次之外,其他数字都出现了两次,请找出这个唯一只出现一次的数字。例如,在…...
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绘画系统,支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美,那么如何搭建部署AI创作ChatGPT?小编这里写一个详细图文教程吧。已支持GPT…...
【服务器数据恢复】昆腾存储中raid5磁盘阵列数据恢复案例
服务器数据恢复环境&故障: 10个磁盘柜,每个磁盘柜配24块硬盘。9个磁盘柜用于存储数据,1个磁盘柜用于存储元数据。 元数据存储中24块硬盘,组建了9组RAID1阵列1组RAID10阵列,4个全局热备硬盘。 数据存储中࿰…...
企业微信变更主体怎么改?
企业微信变更主体有什么作用?现在很多公司都用企业微信来加客户,有时候辛辛苦苦积累了很多客户,但是公司却因为各种各样的原因需要注销,那么就需要通过企业微信变更主体的方法,把企业微信绑定的公司更改为最新的。企业…...
常用生理眼电信号整理合集 (EOG)
目录 Sleep-EDF Sleep-EDF expanded Sleep-EDF 这些信号是从白人男性和女性(21-35 岁)中获得的,没有任何药物治疗;它们包含水平 EOG、FpzCz 和 PzOz EEG,每个采样频率为 100 Hz。 sc* 记录还包含颏下肌电图包络、口鼻…...
【场景题】让你设计一个订单号生成服务,该怎么做?
方案 当设计订单号生成服务时,我们需要考虑唯一性、数据量、可读性、基因法、可扩展性、高性能和高可用性等多个方面。根据这些考虑,一个简单的订单号生成服务设计方案可以采取以下措施: 使用Snowflake算法或第三方分布式ID生成器ÿ…...
使用GraphView实现简单的绘图工具
ShapeItem代码: 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设计系统(系统采用ssh框架进行设计开发),对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。开发环境为TOMCAT7.0…...
Android minigbm框架普法
Android minigbm框架普法 引言 假设存在这么一个场景,我的GPU的上层实现走的不是标准的Mesa接口,且GPU也没有提专门配套的gralloc和hwcompoer实现。那么我们的Android要怎么使用到EGL和GLES库呢,并且此GPU驱动是支持drm实现的,也有…...
01、MongoDB -- 下载、安装、配置文件等配置 及 副本集配置
目录 MongoDB -- 下载、安装、配置 及 副本集配置启动命令启动 mongodb 的服务器(单机和副本集)启动单机模式的 mongodb 服务器启动副本集的 3 个副本节点(mongodb 服务器) 启动 mongodb 的客户端 MongoDB 下载MongoDB 安装1、解压…...
uniapp中导入css和scss的区别
在项目中编写了一个基础的公共样式 common.scss文件 想要将其 导入到app.vue文件中 第一次使用的是import url(static/common.scss); 编译直接报错,无法识别这个文件 原因是 使用import url()是CSS中用于导入外部样式表的语法,但它不适用于导入SCS…...
RabbitMQ-TTL/死信队列/延迟队列高级特性
文章目录 TTL死信队列消息成为死信的三种情况队列如何绑定死信交换机 延迟队列RabbitMQ如何实现延迟队列 总结来源B站黑马程序员 TTL TTLTTL(Time To Live):存活时间/过期时间当信息到达存活时间后,还没有被消费,会被自动清除。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…...
身份证识别系统(安卓)
设计内容与要求: 通过手机摄像头捕获身份证信息,将身份证上的姓名、性别、出生年月、身份证号码保存在数据库中。1)所开发Apps软件至少需由3-5个以上功能性界面组成。要求:界面美观整洁、方便应用;可以使用Android原生…...
Python教程——最后一波来喽
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1.使用__slots__2. property3.多重继承 4.定制类5.枚举类6.错误处理7.调试8. 文档测试9.单元测试10. 文件读写11. StringIO和BytesIO12. 操作文件和目录13.序列化14…...
学生管理系统(python实现)
新增学生显示学生查找学生删除学生存档到文件 约定好数据的存储格式: 约定把数据保存在和py文件同级目录中,文件名为record.txt 文件内容按照行文本的方式来表示 首先这是一个文本文件,里面包含了很多行,每一行代表一个学生 …...
Java读取文件
读取文件为String 、访问链接直接跳转html 环境:SpringMVC 、前端jsp InputStreamReader FileInputStream fileInputStream new FileInputStream(formatFile.getHtmlpath());InputStreamReader reader new InputStreamReader(fileInputStream, StandardCharsets…...
曾桂华:车载座舱音频体验探究与思考| 演讲嘉宾公布
智能车载音频 I 分论坛将于3月27日同期举办! 我们正站在一个前所未有的科技革新的交汇点上,重塑我们出行体验的变革正在悄然发生。当人工智能的磅礴力量与车载音频相交融,智慧、便捷与未来的探索之旅正式扬帆起航。 在驾驶的旅途中࿰…...
面试题HTML+CSS+网络+浏览器篇
文章目录 Css预处理sass less是什么?为什么使用他们怎么转换 less 为 css?重绘和回流是什么http 是什么?有什么特点HTTP 协议和 HTTPS 区别什么是 CSRF 攻击HTML5 新增的内容有哪些Css3 新增的特性flex VS grid清除浮动的方式有哪些ÿ…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
