LeetCode-Go 题解268. Missing Number缺失数字—— 线性时间异或算法的源码级解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 268 题「Missing Number缺失数字」展开以 leetcode/0268.Missing-Number/README.md 为核心骨架并结合 LeetCode-Go 仓库中该题的 Go 实现与测试用例深入讲解如何利用异或XOR性质在O(n) 线性时间复杂度、O(1) 常数额外空间内找出缺失数字。读完本文你将掌握异或抵消法的推导过程、Go 实现细节、边界情况处理以及如何在本仓库中运行测试验证结果。1. 题目描述Given an array containing n distinct numbers taken from0, 1, 2, ..., n, find the one that is missing from the array.给定一个包含n个互不相同的数字的数组这些数字取自0, 1, 2, ..., n找出数组中缺失的那个数。示例 1Input: [3,0,1] Output: 2示例 2Input: [9,6,4,2,3,5,7,0,1] Output: 8注意你的算法应该具有线性时间复杂度。你能否只使用额外常数空间来实现2. 题目大意给定一个包含0, 1, 2, ..., n中n个数的序列找出0 .. n中没有出现在序列中的那个数。算法应该具有线性时间复杂度并且只能使用额外常数空间。这里需要特别留意两点约束线性时间复杂度即 O(n)意味着不能使用双重循环暴力查找也不能依赖排序基于比较的排序至少 O(n log n)常数额外空间意味着不能引入与 n 线性相关的辅助数组或哈希表。这两条约束直接排除了排序后逐位比对与哈希集合补集两类直观解法指引我们走向位运算。3. 解题思路利用异或性质 X^X 0要求找出0, 1, 2, ..., n中缺失的那个数。这里利用异或的性质X^X 0即同一个数字与自己异或的结果为 0。我们需要构造一个 X用数组下标就可以了。数字下标是从[0, n-1]数字是[0, n]依次把数组里面的数字进行异或把结果和n再异或一次中和掉出现的数字剩下的那个数字就是之前没有出现过的、缺失的数字。3.1 为什么异或可行异或运算满足三条关键性质交换律a ^ b b ^ a结合律(a ^ b) ^ c a ^ (b ^ c)自反性抵消a ^ a 0且a ^ 0 a。现在考虑完整集合[0, 1, 2, ..., n]共 n1 个数与数组nums共 n 个数缺失了其中一个。若我们把这两组数全部异或在一起凡是同时出现在两个集合中的数都会因X^X 0被抵消唯一落单的那个数就是缺失的数字。但完整集合并不需要我们显式构造——数组下标天然就覆盖了[0, n-1]而完整集合中比下标多出来的那个数正是n本身。因此result 0 for i in 0..n-1: result ^ i // 下标部分覆盖 0..n-1 result ^ nums[i] // 数组中的数字 result ^ n // 补上 n最终result即为缺失的数字。3.2 复杂度分析时间复杂度O(n)只需一次线性遍历空间复杂度O(1)只使用了一个整型变量xor。两项指标均严格满足题目的要求。4. 仓库源码实现解析本仓库的 Go 实现位于 leetcode/0268.Missing-Number/268. Missing Number.go完整代码如下package leetcode func missingNumber(nums []int) int { xor, i : 0, 0 for i 0; i len(nums); i { xor xor ^ i ^ nums[i] } return xor ^ i }4.1 逐行剖析第 3 行初始化xor 0异或的零元x ^ 0 x并声明循环变量i第 4-6 行在单次循环内一次性完成xor ^ i ^ nums[i]把下标与数组元素同时异或进结果。这里i的取值区间是[0, n-1]nums[i]是数组中的 n 个数字第 8 行循环结束后i len(nums) nreturn xor ^ i等价于补上数字n的异或。4.2 用一个示例走一遍以nums [3, 0, 1]n 3为例循环步inums[i]xor累加初始--01030 ^ 0 ^ 3 32103 ^ 1 ^ 0 23212 ^ 2 ^ 1 1循环结束3即 n-1 ^ 3 2最终返回 2与题目示例 1 的输出一致。整个过程中出现过的{0, 1, 3}均被抵消剩下唯一未出现的2。4.3 为什么仓库实现如此简洁从源码结构看missingNumber没有做任何边界特判当数组为空n 0时循环不执行直接返回0 ^ 0 0即唯一缺失的数字 0行为依然正确。这正是位运算方案无状态、无分支的特点也是它比数学求差法n*(n1)/2 - sum存在整数溢出风险在工程上更稳健的原因。5. 测试用例验证本仓库为每题都配有同名测试文件本题的测试位于 leetcode/0268.Missing-Number/268. Missing Number_test.go。测试代码采用仓库统一的question268 / para268 / ans268结构组织package leetcode import ( fmt testing ) type question268 struct { para268 ans268 } // para 是参数 // one 代表第一个参数 type para268 struct { s []int } // ans 是答案 // one 代表第一个答案 type ans268 struct { one int } func Test_Problem268(t *testing.T) { qs : []question268{ { para268{[]int{3, 0, 1}}, ans268{2}, }, { para268{[]int{9, 6, 4, 2, 3, 5, 7, 0, 1}}, ans268{8}, }, } fmt.Printf(------------------------Leetcode Problem 268------------------------\n) for _, q : range qs { _, p : q.ans268, q.para268 fmt.Printf(【input】:%v 【output】:%v\n, p, missingNumber(p.s)) } fmt.Printf(\n\n\n) }测试覆盖了两组数据[3, 0, 1]→ 期望输出 2对应题目示例 1n 3缺失 2[9, 6, 4, 2, 3, 5, 7, 0, 1]→ 期望输出 8对应题目示例 2n 9缺失 8。从仓库整体来看README_zh.md 宣称所有题解均达到100% test coverage且gotest.sh脚本通过go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部 leetcode 包统一收集覆盖率本题目所在的 leetcode 包同样包含在这一统计范围内。6. 在仓库中运行与验证6.1 单独运行本题测试在仓库根目录执行go test -v -run Test_Problem268 ./leetcode/-v会输出测试过程中的【input】/【output】打印可以直接对照题目示例核对结果。6.2 运行全部题解测试并生成覆盖率仓库根目录的 gotest.sh 提供了统一验证入口bash gotest.sh脚本会以atomic覆盖模式对整个leetcode目录执行测试并产出coverage.txt。Go 版本要求为 1.19见仓库根目录 go.mod。7. 同类思路延伸异或抵消法不是本题的唯一解法但它是满足线性时间 常数空间双约束下最优雅的一种。其他常见思路对比方案时间复杂度空间复杂度说明异或抵消本仓库实现O(n)O(1)无溢出风险位运算高效数学求和n*(n1)/2 - sum(nums)O(n)O(1)思路直观但 n 较大时求和可能溢出 int排序后比对下标O(n log n)O(1)不满足线性时间约束哈希集合求补集O(n)O(n)不满足常数空间约束异或方案同时规避了整数溢出与额外空间两个隐患这也是 LeetCode-Go 仓库采用它的原因。小结本题的核心收获在于当题目要求线性时间 常数空间时优先考虑位运算。利用X^X 0的自反性以数组下标补全完整区间即可在一次遍历中定位缺失元素。仓库中 268. Missing Number.go 仅用 6 行代码就实现了这一思路配合 268. Missing Number_test.go 的用例构成了一个完整、可验证的最小题解单元可直接作为面试中该题的标准答案模板。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解：268. Missing Number（缺失数字）—— 线性时间异或算法的源码级解析
LeetCode-Go 题解268. Missing Number缺失数字—— 线性时间异或算法的源码级解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 268 题「Missing Number缺失数字」展开以 leetcode/0268.Missing-Number/README.md 为核心骨架并结合 LeetCode-Go 仓库中该题的 Go 实现与测试用例深入讲解如何利用异或XOR性质在O(n) 线性时间复杂度、O(1) 常数额外空间内找出缺失数字。读完本文你将掌握异或抵消法的推导过程、Go 实现细节、边界情况处理以及如何在本仓库中运行测试验证结果。1. 题目描述Given an array containing n distinct numbers taken from0, 1, 2, ..., n, find the one that is missing from the array.给定一个包含n个互不相同的数字的数组这些数字取自0, 1, 2, ..., n找出数组中缺失的那个数。示例 1Input: [3,0,1] Output: 2示例 2Input: [9,6,4,2,3,5,7,0,1] Output: 8注意你的算法应该具有线性时间复杂度。你能否只使用额外常数空间来实现2. 题目大意给定一个包含0, 1, 2, ..., n中n个数的序列找出0 .. n中没有出现在序列中的那个数。算法应该具有线性时间复杂度并且只能使用额外常数空间。这里需要特别留意两点约束线性时间复杂度即 O(n)意味着不能使用双重循环暴力查找也不能依赖排序基于比较的排序至少 O(n log n)常数额外空间意味着不能引入与 n 线性相关的辅助数组或哈希表。这两条约束直接排除了排序后逐位比对与哈希集合补集两类直观解法指引我们走向位运算。3. 解题思路利用异或性质 X^X 0要求找出0, 1, 2, ..., n中缺失的那个数。这里利用异或的性质X^X 0即同一个数字与自己异或的结果为 0。我们需要构造一个 X用数组下标就可以了。数字下标是从[0, n-1]数字是[0, n]依次把数组里面的数字进行异或把结果和n再异或一次中和掉出现的数字剩下的那个数字就是之前没有出现过的、缺失的数字。3.1 为什么异或可行异或运算满足三条关键性质交换律a ^ b b ^ a结合律(a ^ b) ^ c a ^ (b ^ c)自反性抵消a ^ a 0且a ^ 0 a。现在考虑完整集合[0, 1, 2, ..., n]共 n1 个数与数组nums共 n 个数缺失了其中一个。若我们把这两组数全部异或在一起凡是同时出现在两个集合中的数都会因X^X 0被抵消唯一落单的那个数就是缺失的数字。但完整集合并不需要我们显式构造——数组下标天然就覆盖了[0, n-1]而完整集合中比下标多出来的那个数正是n本身。因此result 0 for i in 0..n-1: result ^ i // 下标部分覆盖 0..n-1 result ^ nums[i] // 数组中的数字 result ^ n // 补上 n最终result即为缺失的数字。3.2 复杂度分析时间复杂度O(n)只需一次线性遍历空间复杂度O(1)只使用了一个整型变量xor。两项指标均严格满足题目的要求。4. 仓库源码实现解析本仓库的 Go 实现位于 leetcode/0268.Missing-Number/268. Missing Number.go完整代码如下package leetcode func missingNumber(nums []int) int { xor, i : 0, 0 for i 0; i len(nums); i { xor xor ^ i ^ nums[i] } return xor ^ i }4.1 逐行剖析第 3 行初始化xor 0异或的零元x ^ 0 x并声明循环变量i第 4-6 行在单次循环内一次性完成xor ^ i ^ nums[i]把下标与数组元素同时异或进结果。这里i的取值区间是[0, n-1]nums[i]是数组中的 n 个数字第 8 行循环结束后i len(nums) nreturn xor ^ i等价于补上数字n的异或。4.2 用一个示例走一遍以nums [3, 0, 1]n 3为例循环步inums[i]xor累加初始--01030 ^ 0 ^ 3 32103 ^ 1 ^ 0 23212 ^ 2 ^ 1 1循环结束3即 n-1 ^ 3 2最终返回 2与题目示例 1 的输出一致。整个过程中出现过的{0, 1, 3}均被抵消剩下唯一未出现的2。4.3 为什么仓库实现如此简洁从源码结构看missingNumber没有做任何边界特判当数组为空n 0时循环不执行直接返回0 ^ 0 0即唯一缺失的数字 0行为依然正确。这正是位运算方案无状态、无分支的特点也是它比数学求差法n*(n1)/2 - sum存在整数溢出风险在工程上更稳健的原因。5. 测试用例验证本仓库为每题都配有同名测试文件本题的测试位于 leetcode/0268.Missing-Number/268. Missing Number_test.go。测试代码采用仓库统一的question268 / para268 / ans268结构组织package leetcode import ( fmt testing ) type question268 struct { para268 ans268 } // para 是参数 // one 代表第一个参数 type para268 struct { s []int } // ans 是答案 // one 代表第一个答案 type ans268 struct { one int } func Test_Problem268(t *testing.T) { qs : []question268{ { para268{[]int{3, 0, 1}}, ans268{2}, }, { para268{[]int{9, 6, 4, 2, 3, 5, 7, 0, 1}}, ans268{8}, }, } fmt.Printf(------------------------Leetcode Problem 268------------------------\n) for _, q : range qs { _, p : q.ans268, q.para268 fmt.Printf(【input】:%v 【output】:%v\n, p, missingNumber(p.s)) } fmt.Printf(\n\n\n) }测试覆盖了两组数据[3, 0, 1]→ 期望输出 2对应题目示例 1n 3缺失 2[9, 6, 4, 2, 3, 5, 7, 0, 1]→ 期望输出 8对应题目示例 2n 9缺失 8。从仓库整体来看README_zh.md 宣称所有题解均达到100% test coverage且gotest.sh脚本通过go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部 leetcode 包统一收集覆盖率本题目所在的 leetcode 包同样包含在这一统计范围内。6. 在仓库中运行与验证6.1 单独运行本题测试在仓库根目录执行go test -v -run Test_Problem268 ./leetcode/-v会输出测试过程中的【input】/【output】打印可以直接对照题目示例核对结果。6.2 运行全部题解测试并生成覆盖率仓库根目录的 gotest.sh 提供了统一验证入口bash gotest.sh脚本会以atomic覆盖模式对整个leetcode目录执行测试并产出coverage.txt。Go 版本要求为 1.19见仓库根目录 go.mod。7. 同类思路延伸异或抵消法不是本题的唯一解法但它是满足线性时间 常数空间双约束下最优雅的一种。其他常见思路对比方案时间复杂度空间复杂度说明异或抵消本仓库实现O(n)O(1)无溢出风险位运算高效数学求和n*(n1)/2 - sum(nums)O(n)O(1)思路直观但 n 较大时求和可能溢出 int排序后比对下标O(n log n)O(1)不满足线性时间约束哈希集合求补集O(n)O(n)不满足常数空间约束异或方案同时规避了整数溢出与额外空间两个隐患这也是 LeetCode-Go 仓库采用它的原因。小结本题的核心收获在于当题目要求线性时间 常数空间时优先考虑位运算。利用X^X 0的自反性以数组下标补全完整区间即可在一次遍历中定位缺失元素。仓库中 268. Missing Number.go 仅用 6 行代码就实现了这一思路配合 268. Missing Number_test.go 的用例构成了一个完整、可验证的最小题解单元可直接作为面试中该题的标准答案模板。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
