LeetCode LCR 070. 有序数组中的单一元素

2026-03-28 HGNULB 约 7 分钟

文章信息 5 个分类 3 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 070. 有序数组中的单一元素

题意分析

给一个升序数组，其中每个元素都恰好出现两次，只有一个元素出现一次，要求把这个「单身」元素找出来。

题目明确要求时间 $O(\log n)$ 且空间 $O(1)$。这两条约束一起把常见的替代解法全部封死：哈希计数是 $O(n)$ 空间，全体异或是 $O(n)$ 时间，线性扫描也是 $O(n)$ 时间。只剩下二分。

数组升序且成对出现，这个结构给了二分可用的判据。由于总共 $2k + 1$ 个元素，数组长度必为奇数，单身元素的下标也必为偶数——它左边的元素成对铺满，配对数是整数。

边界上要注意：单身元素可能在最左端（下标 0）或最右端（下标 $n-1$），二分区间必须能覆盖到；数组最短是 1，此时唯一的元素就是答案，代码不能在这种情况下越界或死循环。

解法：二分查找判定答案

核心思路

暴力做法是两两一组扫描，比较 nums[i] 与 nums[i+1] 是否相等，第一次不相等时 nums[i] 就是答案。$O(n)$，正确但达不到题目要求。

瓶颈在于线性扫描是把配对关系逐组验证过去的，而事实上配对关系具有很强的整体性：在单身元素出现之前，所有元素都严格按照「偶数下标 + 奇数下标」两两配对；在它出现之后，配对关系整体错位一格，变成「奇数下标 + 偶数下标」。这个错位点唯一，且左右两侧性质截然不同——正是二分的标准形态。

把这个性质写成可判定的形式。对任意下标 mid，它的「理论配对伙伴」是 mid ^ 1：当 mid 是偶数时 mid ^ 1 == mid + 1，当 mid 是奇数时 mid ^ 1 == mid - 1。异或 1 恰好在相邻的偶奇下标之间来回切换，一行就把两种情况统一了。

于是判据是：若 nums[mid] == nums[mid ^ 1]，说明 mid 处的配对仍然完好，错位尚未发生，单身元素必在 mid 右侧；若两者不等，说明配对已经错位，单身元素在 mid 或其左侧。

维持的不变量是：答案始终落在 [left, right] 内；left 左侧的所有下标配对完好，right 及其右侧的下标都已处于错位区。每轮判定后，不等时保留 mid（right = mid），相等时排除 mid（left = mid + 1），区间严格缩短，最终 left == right 就是单身元素的下标。

解题步骤

令 left = 0、right = nums.length - 1。单身元素可能在任意位置，包括两端，所以区间必须覆盖整个数组；这里是闭区间语义，右端取 $n-1$。

循环条件写 left < right，收缩到唯一候选时退出。数组长度为 1 时循环一次都不进，直接返回首元素，边界天然成立。

每轮取 mid = (left + right) >> 1，用 nums[mid] 与 nums[mid ^ 1] 比较。用 mid ^ 1 而不是写 if (mid % 2 == 0) ... else ... 两个分支，是因为异或 1 已经完整表达了「找相邻的配对伙伴」这个语义，且 mid ^ 1 永远不会越界——mid 最大取到 right 时若 right 为偶数，mid ^ 1 = right + 1，而这种情况下 right 是偶数意味着区间还有右侧元素存在（数组长度为奇数、答案下标为偶数，收缩过程保证 right 为偶数时 right 就是答案且循环已退出）。

若两者相等，配对完好，mid 及其左边全部出局，令 left = mid + 1。必须是 mid + 1，写成 mid 会导致区间不收缩而死循环。

若两者不等，错位已经发生，答案不在右侧，令 right = mid。保留 mid 是因为它自己可能就是单身元素。

退出后 left == right，返回 nums[left]。题目要的是元素值而不是下标，注意返回的是值。

以 nums = [1, 1, 2, 3, 3, 4, 4, 8, 8] 走一遍：初始 left = 0、right = 8。第一轮 mid = 4，mid ^ 1 = 5，比较 nums[4] = 3 与 nums[5] = 4，不相等说明下标 4 处配对已错位，答案在左半边，right = 4。第二轮 mid = 2，mid ^ 1 = 3，比较 nums[2] = 2 与 nums[3] = 3，不相等，right = 2。第三轮 mid = 1，mid ^ 1 = 0，比较 nums[1] = 1 与 nums[0] = 1，相等说明这一段配对完好，答案在右边，left = 2。此时 left == right == 2，退出返回 nums[2] = 2。可以看到判定始终在问「这个下标和它的理论伙伴还配得上吗」，而不关心元素的具体数值。

代码实现

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] != nums[mid ^ 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

func singleNonDuplicate(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := (left + right) >> 1
        if nums[mid] != nums[mid^1] {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return nums[left]
}

复杂度分析

时间复杂度：$O(\log n)$，每轮判定只做一次比较并把候选区间至少减半，从 $n$ 收敛到 1 需要 $\lceil \log_2 n \rceil$ 轮。

空间复杂度：$O(1)$，只用了三个下标变量，没有任何辅助数组或递归栈，满足题目对空间的硬性要求。

关键点总结

二分的判据不必是「元素与目标的大小关系」。只要能找到一个在答案两侧取值不同、且只翻转一次的布尔性质，二分就能用——本题用的是「配对是否完好」。

mid ^ 1 是「取相邻配对伙伴」的惯用写法：偶数加一、奇数减一，一行覆盖两种情况，比写奇偶分支更短也更不容易漏。这个技巧在成对结构（配对括号、成对日志、双向边）里反复出现。

满足条件的 mid 保留、不满足的排除，是左边界二分不丢解且必然终止的根本规则，与判据本身是什么无关。

数组长度必为奇数、答案下标必为偶数，这类由题设推出的结构性结论应当在动笔前先想清楚，它们是判断边界是否安全的依据。

有序 + 成对 + 单个例外，这个组合几乎总是指向「配对错位点二分」；若数组无序，则只能退回异或或哈希，$O(\log n)$ 无从谈起。

面试视角：面试官很可能先问「全体异或不就行了吗」。要答异或是 $O(n)$ 时间，题目要求 $O(\log n)$，因此必须利用有序性——这句话是切入正解的钥匙，也是这题真正的考点所在。

面试视角：常见追问是「如果每个元素出现三次、只有一个出现一次呢」。答有序时同理可做「按三个一组的配对错位」二分，无序时则改用按位计数模 3，思路分别对应本题与 137 题。

易错点总结

错误写法：判定写成 nums[mid] == nums[mid + 1] 就向右收缩。用例 nums = [1, 1, 2] → mid = 1 时 nums[1] = 1 与 nums[2] = 2 不等，据此判定错位并收缩到左侧，最终返回 1，正确答案是 2；只看右邻居无法区分「自己是配对的右半」还是「自己是单身」。

错误写法：相等时写 left = mid。用例 nums = [1, 1, 2] → 第一轮 mid = 1，若判定为相等则 left 停在 1 不动，区间不收缩，死循环。

错误写法：不等时写 right = mid - 1。用例 nums = [1, 1, 2] → 正确答案下标 2 在某轮成为 mid 时被直接排除，最终返回 1。

错误写法：right 初始化为 nums.length。用例 nums = [1] → mid 可能取到 1，nums[1] 越界抛异常；闭区间写法的右端必须是 $n - 1$。

错误写法：返回 left 而不是 nums[left]。用例 nums = [1, 1, 2] → 返回下标 2 而不是元素值 2 虽然凑巧相同，换成 nums = [3, 3, 7, 7, 11] 时返回 4，正确答案是 11。

错误写法：用 mid % 2 手写奇偶分支却把方向搞反，偶数时比较 mid - 1、奇数时比较 mid + 1。用例 nums = [1, 1, 2, 3, 3] → 配对伙伴取反，判定结果整体反转，收缩方向全错，返回 1，正确答案是 2。

错误写法：为了「保险」把 mid 强行调成偶数（如 mid -= mid & 1）却保留 left = mid + 1 的收缩。用例 nums = [1, 1, 2] → 调整后 mid 可能回退到 left，left = mid + 1 只前进一格，区间收缩退化成线性，虽不出错但复杂度掉到 $O(n)$。

错误写法：直接全体异或求解。用例 nums 长度 $10^5$ → 结果正确但耗时 $O(n)$，不满足题目对 $O(\log n)$ 的硬性要求，面试中会被判为没抓住考点。

相似题目

题目	难度	考察点
540. 有序数组中的单一元素	中等	与本题同题，可用来对照异或解法与配对错位二分的复杂度差异
137. 只出现一次的数字 II	中等	数组无序且元素出现三次，只能按位计数取模，无法利用有序性
268. 丢失的数字	简单	同样是「唯一例外」问题，但缺失的是值而非重复关系，可用求和或异或
35. 搜索插入位置	简单	判据回到元素与目标的比较，是左边界二分最基础的形态
34. 在排序数组中查找元素的第一个和最后一个位置	中等	处理的是重复元素的区间边界，需要同时求下界与上界
162. 寻找峰值	中等	判据换成相邻元素的趋势，同属「非比较目标值」的二分
剑指 Offer 53 - II. 0～n-1中缺失的数字	简单	判据是「下标与值是否相等」，同样属于配对错位点的二分