教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文基于 AlgoNote 仓库的题解文档 single-element-in-a-sorted-array.md完整讲解 LeetCode 第 540 题「有序数组中的单一元素」的二分查找解法。这道题的精髓在于数组整体有序且元素成对出现只有唯一一个落单元素利用下标奇偶性规律即可在 $O(\log n)$ 时间内定位该元素同时满足 $O(1)$ 空间复杂度。读完本文你将掌握利用奇偶索引规律改造二分查找这一类高频面试技巧并能理解它与仓库中 二分查找基础教程 一脉相承的减而治之思想。题目信息题目编号0540. 有序数组中的单一元素Single Element in a Sorted Array标签数组、二分查找难度中等仓库位置题解文档同时收录于 0500-0599 题解索引 与 题解总列表题目大意与约束描述给定一个仅由整数组成的有序数组其中每个元素都会出现两次唯有一个数只会出现一次。要求找出并返回只出现一次的那个数。说明关键约束设计的解决方案必须满足 $O(\log n)$ 时间复杂度和 $O(1)$ 空间复杂度。这条约束直接排除了遍历统计哈希计数等 $O(n)$ 方案把解题方向逼向二分查找。$1 \le nums.length \le 10^{5}$。注意数组长度恒为奇数$2k1$ 个元素 $k$ 对 1 个落单元素。$0 \le nums[i] \le 10^{5}$。示例示例 1输入: nums [1,1,2,3,3,4,4,8,8] 输出: 2示例 2输入: nums [3,3,7,7,10,11,11] 输出: 10解题思路二分查找核心观察奇偶索引的配对规律由于数组是有序的且除一个元素外其他元素都出现两次成对出现的元素必然相邻排列如[1,1]、[3,3]。因此可以得出关键规律在单一元素之前所有成对出现的元素中第一个元素出现在偶数索引第二个元素出现在奇数索引。即对于一对(nums[i], nums[i1])i为偶数、i1为奇数。在单一元素之后这个规律会反转。因为落单元素占据了第一个位置导致其后的每一对元素整体偏移一位变成第一个元素在奇数索引、第二个元素在偶数索引。以示例 1 的nums [1,1,2,3,3,4,4,8,8]为例索引012345678数值112334488配对偶奇落单奇偶奇偶奇偶可见落单元素2之前的对子1和1符合偶-奇配对落单元素之后的对子3,3、4,4、8,8全部反转为奇-偶配对。奇偶配对规律发生翻转的那个分界点正是单一元素所在的位置这一性质天然具备二分单调性可直接驱动二分查找。具体算法步骤初始化左右边界left 0right len(nums) - 1维护左闭右闭区间[left, right]。当left right时循环计算中点mid (left right) // 2。若mid为偶数正常情况下nums[mid]应与其右邻nums[mid1]配对。若nums[mid] nums[mid 1]说明落单元素在右半部分令left mid 2跳过这一对否则说明落单元素在左半部分含mid令right mid。若mid为奇数正常情况下nums[mid]应与其左邻nums[mid-1]配对。若nums[mid] nums[mid - 1]说明落单元素在右半部分令left mid 1否则说明落单元素在左半部分含mid令right mid - 1。循环结束时left rightnums[left]即为答案。这里的区间收缩方式与仓库 二分查找二 中介绍的「排除法」一脉相承每轮通过配对关系排除掉落单元素一定不存在的一半区间符合二分查找减而治之的核心思想见 二分查找一 的 1.3 节。注意由于本题在偶数mid命中时采用left mid 2跳过整对元素区间长度始终为奇数因此使用向下取整的mid不会引发死循环循环条件用left right即可安全收敛。思路 1代码class Solution: def singleNonDuplicate(self, nums: List[int]) - int: left, right 0, len(nums) - 1 while left right: mid (left right) // 2 # 如果 mid 是偶数应该和 mid1 配对 # 如果 mid 是奇数应该和 mid-1 配对 if mid % 2 0: # 偶数索引检查是否和下一个元素相等 if mid 1 len(nums) and nums[mid] nums[mid 1]: # 单一元素在右半部分 left mid 2 else: # 单一元素在左半部分包括 mid right mid else: # 奇数索引检查是否和前一个元素相等 if nums[mid] nums[mid - 1]: # 单一元素在右半部分 left mid 1 else: # 单一元素在左半部分包括 mid right mid - 1 return nums[left]代码要点说明mid % 2 0分支中mid 1 len(nums)的判界当mid恰为最后一个偶数索引时不会越界访问同时该条件下nums[mid] nums[mid 1]若成立则必然把区间推向右侧实际上由于数组长度恒为奇数且落单元素存在偶数mid处未命中配对时走right mid分支即可正确收敛。循环使用left right而非left right保证结束时left right无需区分返回left还是right这与仓库二分查找教程 01_14 的 4.3 节「排除法」 中推荐的写法一致。思路 1复杂度分析时间复杂度$O(\log n)$其中 $n$ 是数组长度。每轮循环区间缩小约一半至多 $\lceil \log_2 n \rceil$ 次迭代。空间复杂度$O(1)$只使用了常数额外空间未借助任何辅助数组或哈希表。延伸讨论为什么不能只用异或与 0136. 只出现一次的数字标签位运算、数组难度简单不同540 题不能仅靠异或通关。仓库 0136 题解 给出了异或解法利用异或的三大性质a ^ 0 a、a ^ a 0、交换律与结合律对数组全部元素做一遍ans ^ nums[i]成对元素互相抵消最终剩下落单元素——这依赖 位运算教程 中介绍的「按位异或^」运算。但请注意异或解法的时间复杂度是 $O(n)$它只能满足 540 题的空间约束 $O(1)$无法满足题目明确要求的 $O(\log n)$ 时间约束。因此若题目不要求$O(\log n)$如 136 题异或是更简洁的写法3 行代码若题目强制$O(\log n)$如本题 540则必须使用上述基于奇偶索引规律的二分查找。这种同一类问题在不同复杂度约束下需要换武器的对比正是算法面试中常见的考察点。作为知识延伸可将异或写法用于自测class Solution: def singleNonDuplicate(self, nums: List[int]) - int: ans 0 for x in nums: ans ^ x return ans该写法仅用于理解异或特性不满足本题 $O(\log n)$ 要求不应作为最终提交答案。同类二分查找题目扩展本题是利用数组性质设计二分的典型代表与本仓库其他二分题目形成完整训练链路可参考 二分查找题目列表入门0704. 二分查找、0035. 搜索插入位置边界类0034. 在排序数组中查找元素的第一个和最后一个位置、0278. 第一个错误的版本旋转数组类0033. 搜索旋转排序数组、0153. 寻找旋转排序数组中的最小值、0154. 寻找旋转排序数组中的最小值 II峰值类0162. 寻找峰值进阶0287. 寻找重复数小结LeetCode 0540「有序数组中的单一元素」是一道将有序性 成对性两条线索巧妙结合的中等难度二分查找题考察点集中在三处观察力能否发现落单元素之前偶-奇配对、之后奇-偶配对的翻转规律二分实现细节mid奇偶分支的配对对象选择、区间收缩步长mid 2/mid 1/mid/mid - 1与循环终止条件left right的正确组合复杂度意识能否意识到异或的 $O(n)$ 解法不满足 $O(\log n)$ 的硬性约束。掌握这道题的奇偶索引二分技巧后再遇到有序 唯一异常元素类问题如峰值查找、旋转数组最小值时就能举一反三快速定位可二分的单调性质在哪里。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐uBlock Origin5 分钟装好免费的广告与跟踪拦截器uBlock Origin5 分钟装好免费的广告与跟踪拦截器 uBlock Origin 是一款免费开源的浏览器扩展它能在广告请求、跟踪脚本和恶意代码加载进网络安全应用安全LeetCode 0004《寻找两个正序数组的中位数》基于二分查找的 O(log(mn)) 解法详解AlgoNote 算法通关手册LeetCode 0004《寻找两个正序数组的中位数》基于二分查找的 O log mn 解法详解AlgoNote 算法通关手册 导读 本篇技术指南围绕「教程文档知识库AlgoNote 题解LeetCode 0275. H 指数 II有序数组上的对数级二分查找AlgoNote 题解LeetCode 0275. H 指数 II有序数组上的对数级二分查找 本篇是「算法通关手册」AlgoNote 题解库 https教程文档知识库上一篇3大秘籍Vue.Draggable项目如何用Git Hooks实现自动化代码检查让团队协作效率飙升下一篇AOS Community Edition (aos-ce) 原生同意机制MCP 待批审批、托盘 Socket 协议与安全边界的完整解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考