有序数组中的单一元素 图解题解
这道题到底在问什么
- 输入
- [1,1,2,3,3,4,4,8,8]
- 输出
- 2
先想最直接的笨办法
笨办法谁都会：两两一组看，哪组对不上单的就在那。可数组百万长就慢了。题目特意给了「有序」这个条件，就是在提示你——能二分。（动画第 3 步）
最优解：为什么这么做
一句话答案：LeetCode 540 有序数组中的单一元素：要找的是那个只出现一次的数；它像一根楔子，把右边的配对整体挤后一格，二分时把 mid 对齐偶数、看它和下一格是否成对就能定位，时间 O(log n)、空间 O(1)。
除一个数外全部成对，到底在找谁
给一个升序（从小到大排好）的整数数组，除一个数只出现一次外，其余每个数都恰好挨着出现两次。要在 O(log n) 时间、O(1) 空间里找出这个数，不许从头扫一遍。题面例子 nums=[1,1,2,3,3,4,4,8,8]，成对的是 1、3、4、8，落单的是 2，返回 2。
两两一组扫过去，为什么摸不到 O(log n)
一个直白的办法是从头两两一组看，哪组对不上，落单的就在那。数组有 n 个数，最坏要看到接近末尾那组才发现，比满约 n 次，是 O(n)。n 涨到百万就得看百万组，题目点名的 O(log n) 把这条路堵死；就算改用全体异或抵消也还是 O(n)，够不着对数要求。
有序又成对，凭什么能砍掉一半
钥匙在『成对』留下的下标规律上。没有那个落单的数时，每对的第一个都在偶数下标、第二个在紧跟的奇数下标：0、1 一对，2、3 一对，一路整齐。插进来一个落单的数，它像一根楔子，把右边所有的对整体往后挤一格——楔子右边，每对的第一个反倒跑到了奇数下标。
于是整根数组以落单的数为界：界左边『偶数下标和它下一格相等』一直成立，界右边这条规律一破就再不复原。正因为界单调，才能二分——每轮只留还可能藏落单数的那半，另一半整片丢掉。
mid 跟谁比、往哪半收，奇偶怎么摆平
用 lo、hi 两个指针圈住还没排除的范围，起初 lo=0、hi=len(nums)−1。每轮取 mid=(lo+hi)//2，比之前先摆到偶数下标：mid 是奇数就 mid−=1 退回前一格，好让 mid 和 mid+1 凑成一对。再看 nums[mid] 和 nums[mid+1]：相等说明这对规矩、落单数在右，lo 跳到 mid+2 跨过它；不相等说明偶数位配对已乱、落单数就在 mid 或更左，hi 收到 mid（mid 自己可能是答案，别减 1）。循环写 while lo<hi，缩到 lo、hi 撞上那格就是答案。
拿 [1,1,2,3,3,4,4,8,8] 手动收三轮
起点 lo=0、hi=8。第一轮 mid=4 是偶数不用动，nums[4]=3 与 nums[5]=4 不相等，落单数在左，hi 收到 4。第二轮 lo=0、hi=4，mid=2 仍是偶数，nums[2]=2 与 nums[3]=3 不相等，hi 再收到 2。第三轮 lo=0、hi=2，mid=(0+2)//2=1 是奇数，先 mid−=1 退到 0，nums[0]=1 与 nums[1]=1 相等，落单数在右，lo 跳到 mid+2=2。此时 lo=hi=2 撞上，循环停，返回 nums[2]=2。
配对当场比错，就因为 mid 落奇数位没退回
两处一步走错答案就偏了。mid 落奇数位却不退回偶数，nums[mid] 会跟前一对的尾巴去比，成对前提整个塌掉、结论全反，补上 mid−=1 才稳。收右指针若写成 hi=mid−1，碰上 mid 正好是落单数那轮就被跳过去、收敛到错格，得写 hi=mid。每轮范围减半，n 个数最多 log₂n 轮，时间 O(log n)；全程只动 lo、hi、mid 三指针，空间 O(1)。
▶ 动画逐步走查（共 23 步）——想跟着动画一帧帧对照就展开
- 3笨办法谁都会：两两一组看，哪组对不上单的就在那。可数组百万长就慢了。题目特意给了「有序」这个条件，就是在提示你——能二分。
- 4这是全题的命根子。单一元素像一根楔子插进队列，把它后面所有配对整体往右挤了一格，配对的「奇偶节奏」就此被打乱。下面用图把这个节奏画出来。
- 5只要把 mid 永远对齐到偶数下标，再看它和下一格是不是一对：是一对，说明楔子还在右边；不是一对，说明楔子就在 mid 这里或更左。盯住下面 lo/hi/mid 三根指针怎么收缩。
- 6每对的第一个 = 偶数下标先肉眼感受节奏。最左这一对 1、1：第一个 1 在下标 0(偶数)，它的搭档紧跟在下标 1。单一元素左边的每一对都这样——左半边在偶数位、右半边在奇数位。
- 7下标 2 的 2 是单身，打乱节奏走到下标 2，2 找不到搭档——它就是那根楔子。从它往后(已变灰的部分)，所有配对被它顶得整体右移一格，奇偶节奏从这里被掰断。
- 8每对的第一个 = 奇数下标看楔子右边的第一对 3、3：第一个 3 跑到了下标 3(奇数)！节奏反过来了——右半边在偶数位、左半边在奇数位。这个「奇偶翻转点」正是单一元素的位置，二分要找的就是它。
- 9lo=0, hi=n−1=8正式开二分。lo 指数组头(下标 0)、hi 指数组尾(下标 8)，单一元素一定落在这两根指针之间。我们要靠上面那条「偶数下标配对」规则，一轮轮把这个区间砍半。
- 10mid = (0+8)/2 = 4取中点 mid=(0+8)/2=4。它正好是偶数下标，不用调整。规则要求 mid 必须落在偶数位，所以下一步要先检查这点。
- 11mid=4 已是偶数，无需−1mid=4 是偶数，直接拿它和右邻 arr[5] 组成一对(紫底窗口 [4,5])。如果 mid 是奇数，就要先 mid−1 退回偶数位再配对——这是不能省的一步。
- 12arr[4]=3 ≠ arr[5]=4 → 没配上arr[4]=3 和 arr[5]=4 对不上！偶数位的配对被打乱了，说明楔子就在 mid 这里或它左边。所以收右指针：hi = mid = 4，mid 本身可能是答案，不能丢。
- 13排除下标 5~8，hi → 4hi 收到 4，右半截下标 5~8 整段变灰出局。一刀砍掉一半，区间缩成 [0,4]。注意是 hi=mid 不是 mid−1，因为 mid=4 自己还可能就是楔子。
- 14mid = (0+4)/2 = 2新区间 [0,4] 重新取中点，mid=(0+4)/2=2。又是偶数，省心。继续按规则配对。
- 15看 arr[2] 与 arr[3]mid=2 偶数，配上右邻成窗口 [2,3]，里头是 arr[2]=2 与 arr[3]=3。比一比这一对是否相等。
- 16arr[2]=2 ≠ arr[3]=3 → 没配上arr[2]=2 ≠ arr[3]=3，又没配上。和第 1 轮一个道理：偶数位配对乱了，楔子在 mid 或更左。再次收右指针 hi=mid=2。
- 17排除下标 3~4，hi → 2hi 收到 2，下标 3、4 再变灰出局。区间又砍半，缩成 [0,2]。两轮下来 9 个数只剩 3 个候选了。
- 18mid = (0+2)/2 = 1区间 [0,2] 取中点，mid=(0+2)/2=1——这回是奇数！规则规定配对必须从偶数位起，所以这一步还不能直接比，得先把 mid 拨回偶数。
- 19mid 是奇数 → mid−1 = 0mid 是奇数，执行 mid = mid−1 = 0，把它退回最近的偶数下标。现在 mid 指 0，可以放心配对了。这一步正是很多人写错二分的地方。
- 20看 arr[0] 与 arr[1]对齐后从 mid=0 配出窗口 [0,1]，里头是 arr[0]=1 与 arr[1]=1。这一对看起来很整齐，比一下。
- 21arr[0]=1 == arr[1]=1 → 配上了！arr[0]=1 == arr[1]=1，配上了！偶数位的配对完好，说明从这里到 mid+1 都是规规矩矩成对的，楔子在右边。所以推左指针 lo = mid+2 = 2，跳过这完整的一对。
- 22排除下标 0~1，lo → 2lo 跳到 2(跨过 0、1 这完整一对)，下标 0、1 变灰出局。现在 lo 和 hi 都指向 2，下一步它们就要撞上，二分该停了。
- 23lo == hi，停！答案下标 = 2lo 和 hi 撞到一起，循环条件 lo<hi 不再成立，二分停下。区间收成单独一个下标 2——所有成对的数都被排除了，剩下的这一个孤点就是单一元素。
- 24arr[2] = 2返回 arr[2] = 2，正是那个落单的数。9 个元素只比了 3 轮配对就锁定，全程 O(log n)，没有一次多余的扫描。
- 28[3,3,7,7,10,11,11] → 答案 10换个楔子靠右的例子 [3,3,7,7,10,11,11]：偶数位的 (0,1)、(2,3) 都配上 → lo 不断右推，最后停在下标 4，arr[4]=10。右边 11、11 又成对，刚好夹出 10。
⚠️ 容易写错的地方
✗ 错：mid 不对齐偶数就直接配对
✓ 对：mid 为奇数时 mid −= 1
规则建立在「每对第一个在偶数位」上，mid 落奇数位会比错搭档
✗ 错：没配上时写 hi = mid − 1
✓ 对：写 hi = mid
mid 本身可能就是楔子，减 1 会把答案跳过去
完整代码（Python / C++ / Java）
Python
class Solution:
def singleNonDuplicate(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if mid % 2 == 1: # mid 退回偶数下标
mid -= 1
if nums[mid] == nums[mid + 1]: # 配上 → 楔子在右
lo = mid + 2
else: # 没配上 → 楔子在左(含 mid)
hi = mid
return nums[lo]C++
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) mid -= 1; // 对齐偶数
if (nums[mid] == nums[mid + 1]) // 配上 → 右
lo = mid + 2;
else
hi = mid; // 没配上 → 左
}
return nums[lo];
}
};Java
class Solution {
public int singleNonDuplicate(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) mid -= 1; // 对齐偶数
if (nums[mid] == nums[mid + 1]) // 配上 → 右
lo = mid + 2;
else
hi = mid; // 没配上 → 左
}
return nums[lo];
}
}复杂度
时间复杂度
O(log n)
每轮区间砍半，最多 log n 轮
空间复杂度
O(1)
只用 lo/hi/mid 三个指针，原地完成
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 有序数组中的单一元素 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么落单的数右边，配对的下标奇偶会翻过来？+
因为落单的数占掉了一个本该属于配对的位置。在它左边，每一对老老实实是『偶数下标 + 下一格』；轮到它时，它一个数独占了一个偶数下标，没有搭档，于是它右边所有的对被整体往后顶了一格，第一个成员从偶数下标挪到了奇数下标。这样一来，『偶数下标和它下一格相等』这条判断在落单数左边一直成立、右边一直不成立，中间只有一个翻转点，正好卡在落单的数身上，单调可判，所以能二分。
mid 一定要先对齐偶数下标吗，有没有更省的写法？+
必须对齐，因为整套判断都架在『每对的第一个在偶数位』上，mid 落奇数位直接拿去和下一格比，比的是相邻两对的边界、不是同一对，结论会反。省事的写法是 mid = mid -（mid & 1），一句就把奇数拨成偶数、偶数原样不动，效果和 if 判断再减一完全一样；也可以把二分区间直接限定在偶数下标上，让 mid 天生只取偶数，省掉这次修正。
如果不要求 O(log n)，还有别的解法吗？+
有，而且更好写。把数组里所有数依次异或起来，成对的两个相同的数异或会抵消成 0，最后剩下的就是那个落单的数，时间 O(n)、空间 O(1)，连有序都不需要。它的短板是必须把每个数都过一遍，达不到本题点名的 O(log n)；真要压到对数级，还得回到靠奇偶规律二分的这条路。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 有序数组中的单一元素 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。