LeetCode 0540 有序数组中的单一元素：AlgoNote 二分查找题解（O(log n)）

• 教程
• 文档
• 知识库

导读

本文基于 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}$。注意数组长度恒为奇数（$2k+1$ 个元素 = $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[i+1])，i为偶数、i+1为奇数。
• 在单一元素之后：这个规律会反转。因为落单元素占据了"第一个位置"，导致其后的每一对元素整体偏移一位，变成第一个元素在奇数索引、第二个元素在偶数索引。

以示例 1 的nums = [1,1,2,3,3,4,4,8,8]为例：

可见：落单元素2之前的对子（1和1）符合"偶-奇"配对；落单元素之后的对子（3,3、4,4、8,8）全部反转为"奇-偶"配对。奇偶配对规律发生翻转的那个分界点，正是单一元素所在的位置，这一性质天然具备"二分单调性"，可直接驱动二分查找。

具体算法步骤

1. 初始化左右边界left = 0，right = len(nums) - 1，维护左闭右闭区间[left, right]。
2. 当left < right时循环：
   • 计算中点mid = (left + right) // 2。
   • 若mid为偶数：正常情况下nums[mid]应与其右邻nums[mid+1]配对。
     • 若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。
3. 循环结束时left == right，nums[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 是偶数，应该和 mid+1 配对 # 如果 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「有序数组中的单一元素」是一道将有序性 + 成对性两条线索巧妙结合的中等难度二分查找题，考察点集中在三处：

1. 观察力：能否发现"落单元素之前偶-奇配对、之后奇-偶配对"的翻转规律；
2. 二分实现细节：mid奇偶分支的配对对象选择、区间收缩步长（mid + 2/mid + 1/mid/mid - 1）与循环终止条件left < right的正确组合；
3. 复杂度意识：能否意识到异或的 $O(n)$ 解法不满足 $O(\log n)$ 的硬性约束。

掌握这道题的奇偶索引二分技巧后，再遇到"有序 + 唯一异常元素"类问题（如峰值查找、旋转数组最小值）时，就能举一反三，快速定位"可二分的单调性质"在哪里。

• 教程
• 文档
• 知识库