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

2026-04-10 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 中等未解决需复习 10-20 字节跳动美团阿里巴巴快手腾讯猿辅导拼多多

题目描述

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

题意分析

给一个非递减有序的整数数组，其中恰好有一个元素只出现一次，其余每个元素都出现且仅出现两次，要求找出那个只出现一次的元素。有序意味着相同的两个元素一定紧挨着，这是全部推理的基础。

这道题的关键约束不在数据规模上，而在题面最后那句要求：时间复杂度必须是 $O(\log n)$，空间复杂度必须是 $O(1)$。这句话一出，两种最顺手的解法立刻出局——把整个数组异或一遍得到答案是 $O(n)$，逐对扫描比较 nums[i] 与 nums[i+1] 也是 $O(n)$；它们都正确，但都被时间要求判死。要压到对数级别，就只能在有序性上找可以「整段丢弃」的判据。

其余约束是配套的：$1 \le n \le 10^5$，元素值非负。由「一个元素出现一次、其余各出现两次」可推出数组长度必为奇数，这个隐含事实后面会反复用到；$n = 1$ 时答案就是唯一那个元素，属于必须能正确处理的边界。

还有两处边界要预判：单一元素出现在最左端（如 [1,2,2]）和最右端（如 [1,1,2]）。这两种情形最容易在收缩边界时被漏掉或多跳，写完务必拿它们验一遍。

解法：偶数下标二分

核心思路

单一元素出现前，重复元素总以「偶数下标、奇数下标」配对；单一元素占掉一个位置后，右侧配对整体错一位，变为「奇数下标、偶数下标」。题目要求 $O(\log n)$，因此要二分寻找这个配对规律发生变化的位置，而不是线性异或。

每轮把 mid 向下调整为偶数，只比较 nums[mid] 与 nums[mid + 1]。若相等，这一对完整且位于单一元素之前，可丢弃到 mid + 1；若不等，错位已经发生，答案位于 left..mid，而 mid 自身也可能是答案。

循环不变量：闭区间 [left,right] 始终包含单一元素，左右边界均为偶数，区间长度为奇数。相等时令 left = mid + 2，不等时令 right = mid，都保留这一性质。最终 left == right，唯一剩余位置就是答案。

解题步骤

初始化 left = 0、right = n - 1，在 left < right 时循环。

计算中点；若 mid 为奇数，将其减一，确保它是一个候选数对的起点。

若 nums[mid] == nums[mid + 1]，说明左侧配对完整，令 left = mid + 2。

否则令 right = mid，保留可能就是答案的 mid。

区间收敛后返回 nums[left]。

例如 [1,1,2,3,3,4,4,8,8]：中点 4 与 5 不同，收缩到 [0,4]；中点 2 与 3 不同，收缩到 [0,2]；中点向下对齐为 0，nums[0] == nums[1]，最终收敛到下标 2，答案为 2。

代码实现

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) {
                mid--;
            }
            if (nums[mid] == nums[mid + 1]) {
                // mid 与 mid+1 成对，单一元素在右侧。
                left = mid + 2;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

func singleNonDuplicate(nums []int) int {
    left := 0
    right := len(nums) - 1
    for left < right {
        mid := left + (right-left)/2
        if mid%2 == 1 {
            mid--
        }
        if nums[mid] == nums[mid+1] {
            // 左侧配对完整，答案只能在 mid+2 之后。
            left = mid + 2
        } else {
            right = mid
        }
    }
    return nums[left]
}

复杂度分析

时间复杂度：$O(\log n)$，每轮排除约一半区间。

空间复杂度：$O(1)$，只使用常数个下标变量。

关键点总结

二分判断依据不是数值大小，而是重复元素的配对下标是否错位。

mid 必须向下对齐到偶数下标，才能把 mid、mid + 1 看作一组。

相等时跳过完整的一对；不等时保留 mid。

线性异或虽然正确，但不满足题目明确要求的 $O(\log n)$ 时间。

易错点总结

不把 mid 对齐到偶数下标，会让「相等」的方向含义反转。

将 mid 向上调整可能使 mid + 1 越界；应在奇数时执行 mid--。

相等分支写成 left = mid + 1 会破坏偶数边界，甚至导致区间不再收缩。

不等时写 right = mid - 1 可能跳过恰好位于 mid 的答案。

循环条件必须是 left < right；单点区间继续访问 mid + 1 会越界。

相似题目

题目	难度	考察点
LCR 070. 有序数组中的单一元素	中等	同题的偶数下标二分
136. 只出现一次的数字	简单	无序版的异或消消乐
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分求左右边界
33. 搜索旋转排序数组	中等	局部有序上的二分判据
162. 寻找峰值	中等	靠相邻比较二分
剑指 Offer 53 - II. 0～n-1中缺失的数字	简单	下标与值错位找缺失
704. 二分查找	简单	标准二分模板