企业官网建设流程全解析

LeetCode 540 题解：Single Element in a Sorted Array —— Go 实现基于奇偶下标的二分查找

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南围绕 LeetCode 第 540 题「有序数组中的单一元素」展开，完整讲解如何利用"每个元素恰好出现两次、仅一个元素出现一次"的配对结构，将问题收敛为对数组奇偶下标的二分查找，最终以 O(log n) 时间、O(1) 空间求解。文中给出的实现、测试与覆盖率数据均来自当前仓库 leetcode/0540.Single-Element-in-a-Sorted-Array 目录，读者可对照源码与测试用例复现并验证。

题目回顾

给定一个仅由整数组成的有序数组，其中每个元素都会恰好出现两次，唯独有一个数只会出现一次。要求找出并返回这个只出现一次的数，且解决方案必须满足O(log n) 时间复杂度和O(1) 空间复杂度。

示例 1：

Input: nums = [1,1,2,3,3,4,4,8,8] Output: 2

示例 2：

Input: nums = [3,3,7,7,10,11,11] Output: 10

约束条件：

• 1 <= nums.length <= 100000
• 0 <= nums[i] <= 100000

由于数组已有序且成对重复，最简单的直觉是遍历并逐个比对相邻元素，但那需要 O(n) 时间，不满足题目对 O(log n) 的硬性要求，因此必须借助二分查找。

核心思路：利用数组的配对结构

设唯一出现的元素下标为idx。观察数组的配对规律可以发现：

• idx左边的所有元素都能完美配对：下标为偶数的元素nums[2k]一定等于其右侧相邻的nums[2k+1]；
• idx右边的所有元素配对则整体"错位一格"：因为idx位置单独占了一个名额，其右侧第一个元素落在奇数下标上，所以下标为奇数的nums[2k+1]一定等于其右侧相邻的nums[2k+2]。

换句话说，数组被idx分成两段：左段是"偶数下标与紧随的奇数下标相等"，右段是"奇数下标与紧随的偶数下标相等"。分界点idx正是我们要找的答案，而这个分界点天然满足单调性——在idx左侧任意位置都是正常配对，越过idx后配对立刻异常。这正是可以对idx进行二分查找的依据。

奇偶下标判定法：二分查找的关键观察

对于二分中点mid，按mid的奇偶性分两种情况判断配对是否成立：

1. mid为偶数：按左段的规律，若nums[mid] == nums[mid+1]，说明mid与其右侧元素构成合法配对，单一元素必然出现在mid右侧，即idx > mid，于是收缩左边界left = mid + 1；否则说明配对在mid处已经被打破，单一元素必然在mid及其左侧，收缩右边界right = mid。
2. mid为奇数：按左段的规律，若nums[mid] == nums[mid-1]，说明mid-1与mid构成合法配对，单一元素依然在mid右侧，收缩left = mid + 1；否则打破点位于mid及其左侧，收缩right = mid。

循环结束后left == right，nums[left]即为只出现一次的数。

逐例推演

示例 1：nums = [1,1,2,3,3,4,4,8,8]，答案 2

left=0, right=8 mid=4 (偶数): nums[4]=3 != nums[5]=4 → right=4 mid=2 (偶数): nums[2]=2 != nums[3]=3 → right=2 mid=1 (奇数): nums[1]=1 == nums[0]=1 → left=2 left==right==2 → 返回 nums[2]=2 ✓

示例 2：nums = [3,3,7,7,10,11,11]，答案 10

left=0, right=6 mid=3 (奇数): nums[3]=7 == nums[2]=7 → left=4 mid=5 (奇数): nums[5]=11 != nums[4]=10 → right=5 mid=4 (偶数): nums[4]=10 != nums[5]=11 → right=4 left==right==4 → 返回 nums[4]=10 ✓

可见每一轮都能稳定地将搜索区间缩小一半，且最终收敛到单一元素所在下标。

完整 Go 实现与源码分析

仓库中本题的完整实现位于 540.Single Element in a Sorted Array.go，与 README 中的代码一致：

package leetcode func singleNonDuplicate(nums []int) int { left, right := 0, len(nums)-1 for left < right { mid := (left + right) / 2 if mid%2 == 0 { if nums[mid] == nums[mid+1] { left = mid + 1 } else { right = mid } } else { if nums[mid] == nums[mid-1] { left = mid + 1 } else { right = mid } } } return nums[left] }

实现细节值得注意：

• 函数直接定义在leetcode包中（见 go.mod 的模块声明github.com/halfrost/LeetCode-Go），不依赖仓库的 structures 与 template 辅助包，是纯粹的单文件题解，便于独立阅读与单测；
• mid := (left + right) / 2在left < right的前提下恒有mid < right，因此偶数分支访问nums[mid+1]永远不会越界；
• 奇数分支访问nums[mid-1]时，由于奇数mid >= 1，下标同样安全；
• 数组长度为 1 时循环体不执行，直接返回nums[0]，天然覆盖了"单一元素就是整个数组"的边界情形。

测试用例与覆盖率验证

与源码同目录的测试文件 540.Single Element in a Sorted Array_test.go 采用本仓库统一的question540/para540/ans540结构组织用例，覆盖了三组数据：

1. [1,1,2,3,3,4,4,8,8] → 2（题目示例 1）；
2. [3,3,7,7,10,11,11] → 10（题目示例 2）；
3. [1,1,3,3,5] → 5（答案位于数组末端的边界情况）。

测试中对每个用例调用singleNonDuplicate，若结果与期望不一致会通过t.Fatalf立即失败。仓库根目录的 gotest.sh 使用go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...对整个题解目录生成覆盖率，根目录的 coverage.txt 中可见本文件各代码块的执行计数均非零，即该函数的所有分支（偶数/奇数、配对成立/不成立）都已被用例覆盖。读者可在仓库根目录执行以下命令独立复现验证：

go test -v ./leetcode/0540.Single-Element-in-a-Sorted-Array/

复杂度分析

• 时间复杂度：O(log n)。每一轮迭代将搜索区间缩小一半，n 为数组长度，最多执行约log₂ n次比较；
• 空间复杂度：O(1)。仅使用left、right、mid三个整型变量，不额外占用随输入规模增长的内存。

相比直接遍历或使用异或求值的 O(n) 方案，二分查找在十万级数据规模下优势明显（约束中 n 最大为 100000，二分仅需约 17 次迭代）。

延伸思考：为什么异或法不够，以及相关问题

一个常见的直觉方案是"全员异或"：由于相同元素异或结果为 0，遍历一遍将所有元素异或，剩下的值就是只出现一次的数，代码简洁且仍满足 O(1) 空间，但时间复杂度是 O(n)，不满足本题 O(log n) 的要求。本题之所以能更进一步，正是利用了"有序"与"恰好成对出现"两个额外条件，把问题转化为对配对分界点的二分搜索。

若读者希望继续巩固这一套"利用题目结构性质 + 二分查找"的解题模式，可在仓库中对照阅读同类的有序数组二分题解，例如 0033.Search-in-Rotated-Sorted-Array、0153.Find-Minimum-in-Rotated-Sorted-Array 等，它们同样依赖对数组有序性的深入挖掘来设计二分判定条件。核心方法论是一致的：先找到某种随位置单调变化的"配对是否正常"的判定条件，再用二分快速定位临界点。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go