有序数组中的单一元素 图解题解

这道题到底在问什么

输入

[1,1,2,3,3,4,4,8,8]

输出

2

先想最直接的笨办法

笨办法谁都会：两两一组看，哪组对不上单的就在那。可数组百万长就慢了。题目特意给了「有序」这个条件，就是在提示你——能二分。（动画第 3 步）

最优解：一步一步想明白

1. 3笨办法谁都会：两两一组看，哪组对不上单的就在那。可数组百万长就慢了。题目特意给了「有序」这个条件，就是在提示你——能二分。
2. 4这是全题的命根子。单一元素像一根楔子插进队列，把它后面所有配对整体往右挤了一格，配对的「奇偶节奏」就此被打乱。下面用图把这个节奏画出来。
3. 5只要把 mid 永远对齐到偶数下标，再看它和下一格是不是一对：是一对，说明楔子还在右边；不是一对，说明楔子就在 mid 这里或更左。盯住下面 lo/hi/mid 三根指针怎么收缩。
4. 6每对的第一个 = 偶数下标先肉眼感受节奏。最左这一对 1、1：第一个 1 在下标 0(偶数)，它的搭档紧跟在下标 1。单一元素左边的每一对都这样——左半边在偶数位、右半边在奇数位。
5. 7下标 2 的 2 是单身，打乱节奏走到下标 2，2 找不到搭档——它就是那根楔子。从它往后(已变灰的部分)，所有配对被它顶得整体右移一格，奇偶节奏从这里被掰断。
6. 8每对的第一个 = 奇数下标看楔子右边的第一对 3、3：第一个 3 跑到了下标 3(奇数)！节奏反过来了——右半边在偶数位、左半边在奇数位。这个「奇偶翻转点」正是单一元素的位置，二分要找的就是它。
7. 9lo=0, hi=n−1=8正式开二分。lo 指数组头(下标 0)、hi 指数组尾(下标 8)，单一元素一定落在这两根指针之间。我们要靠上面那条「偶数下标配对」规则，一轮轮把这个区间砍半。
8. 10mid = (0+8)/2 = 4取中点 mid=(0+8)/2=4。它正好是偶数下标，不用调整。规则要求 mid 必须落在偶数位，所以下一步要先检查这点。
9. 11mid=4 已是偶数，无需−1mid=4 是偶数，直接拿它和右邻 arr[5] 组成一对(紫底窗口 [4,5])。如果 mid 是奇数，就要先 mid−1 退回偶数位再配对——这是不能省的一步。
10. 12arr[4]=3 ≠ arr[5]=4 → 没配上arr[4]=3 和 arr[5]=4 对不上！偶数位的配对被打乱了，说明楔子就在 mid 这里或它左边。所以收右指针：hi = mid = 4，mid 本身可能是答案，不能丢。
11. 13排除下标 5~8，hi → 4hi 收到 4，右半截下标 5~8 整段变灰出局。一刀砍掉一半，区间缩成 [0,4]。注意是 hi=mid 不是 mid−1，因为 mid=4 自己还可能就是楔子。
12. 14mid = (0+4)/2 = 2新区间 [0,4] 重新取中点，mid=(0+4)/2=2。又是偶数，省心。继续按规则配对。
13. 15看 arr[2] 与 arr[3]mid=2 偶数，配上右邻成窗口 [2,3]，里头是 arr[2]=2 与 arr[3]=3。比一比这一对是否相等。
14. 16arr[2]=2 ≠ arr[3]=3 → 没配上arr[2]=2 ≠ arr[3]=3，又没配上。和第 1 轮一个道理：偶数位配对乱了，楔子在 mid 或更左。再次收右指针 hi=mid=2。
15. 17排除下标 3~4，hi → 2hi 收到 2，下标 3、4 再变灰出局。区间又砍半，缩成 [0,2]。两轮下来 9 个数只剩 3 个候选了。
16. 18mid = (0+2)/2 = 1区间 [0,2] 取中点，mid=(0+2)/2=1——这回是奇数！规则规定配对必须从偶数位起，所以这一步还不能直接比，得先把 mid 拨回偶数。
17. 19mid 是奇数 → mid−1 = 0mid 是奇数，执行 mid = mid−1 = 0，把它退回最近的偶数下标。现在 mid 指 0，可以放心配对了。这一步正是很多人写错二分的地方。
18. 20看 arr[0] 与 arr[1]对齐后从 mid=0 配出窗口 [0,1]，里头是 arr[0]=1 与 arr[1]=1。这一对看起来很整齐，比一下。
19. 21arr[0]=1 == arr[1]=1 → 配上了！arr[0]=1 == arr[1]=1，配上了！偶数位的配对完好，说明从这里到 mid+1 都是规规矩矩成对的，楔子在右边。所以推左指针 lo = mid+2 = 2，跳过这完整的一对。
20. 22排除下标 0~1，lo → 2lo 跳到 2(跨过 0、1 这完整一对)，下标 0、1 变灰出局。现在 lo 和 hi 都指向 2，下一步它们就要撞上，二分该停了。
21. 23lo == hi，停！答案下标 = 2lo 和 hi 撞到一起，循环条件 lo<hi 不再成立，二分停下。区间收成单独一个下标 2——所有成对的数都被排除了，剩下的这一个孤点就是单一元素。
22. 24arr[2] = 2返回 arr[2] = 2，正是那个落单的数。9 个元素只比了 3 轮配对就锁定，全程 O(log n)，没有一次多余的扫描。
23. 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。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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]

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];
    }
};

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];
    }
}

复杂度

面试官可能追问