LeetCode-Go 题解 0136利用异或运算求解 Single Number只出现一次的数字【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 0136.Single-Number 题解文档 为核心讲解 LeetCode 136「只出现一次的数字」这道经典位运算题目在 LeetCode-Go 仓库中的完整解法。你将掌握异或运算的三大核心性质理解其余元素均出现两次、仅一个元素出现一次这一约束如何天然导向 XOR 解法并看到该思路在仓库中 Single Number II137 与 Single Number III260 上的延伸应用。读完本文你既能写出时间复杂度 O(n)、空间复杂度 O(1) 的 Go 实现也能从源码与测试层面验证其正确性。题目描述给定一个非空整数数组其中每个元素都出现两次除了某个元素只出现一次。找出那个只出现一次的元素。注意算法应当具备线性时间复杂度linear runtime complexity能否不使用额外内存extra memory实现示例 1Input: [2,2,1] Output: 1示例 2Input: [4,1,2,1,2] Output: 4题目小结给定一个非空整数数组除一个元素只出现一次外其余每个元素均出现两次找出那个只出现一次的元素要求算法时间复杂度为线性且不使用额外辅助空间。解题思路从出现两次到异或抵消为什么题目强调其余元素均出现两次题目明确要求不使用辅助空间、只允许线性时间遍历这直接排除了两套常见但不符合约束的方案哈希表计数法遍历数组统计每个数字出现次数再找出现次数为 1 的数字。虽然时间复杂度是 O(n)但需要 O(n) 的额外空间违反空间约束双重循环暴力查找对每个元素再遍历一次数组确认是否唯一虽然空间是 O(1)但时间复杂度为 O(n²)违反时间约束。于是需要一种既不借助容器、又能在线性时间内一次遍历完成筛选的手段。此时题目特意强调一个数字出现一次其他都出现两次这个两次就是解题的钥匙——它恰好对应异或运算XOR的核心性质任何一个数字异或它自己结果都等于 0即 x ^ x 0。由此可以得到三个推论x ^ 0 x任何数与 0 异或保持不变x ^ x 0任何数与自身异或结果为 0异或满足交换律与结合律a ^ b ^ a (a ^ a) ^ b 0 ^ b b运算顺序不影响最终结果。核心思路从头到尾依次异或如果我们从头到尾依次异或数组中的每一个数字那么所有出现两次的数字都会两两抵消为 0最终剩下的结果恰好就是那个只出现一次的数字。以示例 2 的[4,1,2,1,2]为例逐步推演4 ^ 1 ^ 2 ^ 1 ^ 2 4 ^ (1 ^ 1) ^ (2 ^ 2) // 结合律成对的 1 与成对的 2 各自抵消 4 ^ 0 ^ 0 4正因为异或的交换律和结合律成对出现的数字无论相隔多远都会在异或链中相互抵消最终result中只保留唯一的那个数字。利用的性质就是 x ^ x 0。源码实现单次遍历、常数空间仓库中本题的 Go 实现位于 136. Single Number.go核心代码与原题解文档一致package leetcode func singleNumber(nums []int) int { result : 0 for i : 0; i len(nums); i { result ^ nums[i] } return result }代码逻辑非常紧凑用result : 0初始化累积值利用x ^ 0 x保证首轮异或不改变结果单层循环遍历整个数组每次执行result ^ nums[i]循环结束后成对出现的数字全部抵消result即为只出现一次的那个数字整个过程只使用了一个int变量额外空间为O(1)单层循环遍历 n 个元素时间复杂度为O(n)完全满足题目的双重约束。测试验证表驱动用例印证正确性仓库为本题编写了配套测试 136. Single Number_test.go采用标准的表驱动table-driven测试结构用para136承载输入数组、ans136承载期望输出再通过question136结构体组合两者。测试用例完整覆盖了题面给出的两个示例输入数组期望输出[2,2,1]1[4,1,2,1,2]4测试主体遍历用例并调用singleNumber(p.s)与期望值比对同时打印【input】/【output】便于人工核对for _, q : range qs { _, p : q.ans136, q.para136 fmt.Printf(【input】:%v 【output】:%v\n, p, singleNumber(p.s)) }在仓库根目录执行go test相关命令即可运行验证例如go test -v -run Test_Problem136 ./leetcode/0136.Single-Number/...这两个用例虽少但分别覆盖了单元素成对抵消后剩首元素[2,2,1]与目标元素位于数组中间[4,1,2,1,2]两种典型排布足以验证异或解法的正确性。同族问题延伸从出现两次到出现三次与出现两个单数掌握了 136 的异或思路后可以顺藤摸瓜在仓库中探索两个同族问题它们体现了同一数学工具在不同约束下的演进137. Single Number II每个元素出现三次仓库 137. Single Number II.go 处理的是除一个元素外其余元素均出现三次的版本。此时简单的全员异或不再奏效x ^ x ^ x x而非 0需要升级为逐位统计 状态机的思路func singleNumberII(nums []int) int { ones, twos : 0, 0 for i : 0; i len(nums); i { ones (ones ^ nums[i]) ^twos twos (twos ^ nums[i]) ^ones } return ones }ones记录出现 1 次的位、twos记录出现 2 次的位出现 3 次时两个标志位同时清零最终ones即只出现一次的数字。值得注意的是该文件还附带了两套每个元素出现 5 次的拓展实现展示了如何把有限状态机推广到任意出现次数很适合作为进阶阅读。260. Single Number III两个只出现一次的数字仓库 260. Single Number III.go 处理的是除两个元素外其余元素均出现两次的版本。思路是分两步走先全员异或得到diff a ^ b两个目标数字的异或结果非零取diff的最低置位diff -diff作为划分依据a与b在这一位上必然不同按该位是否为 0 把数组分成两组分别异或两组各自剩下的就是a与bdiff -diff // Get its last set bit (lsb) res : []int{0, 0} for _, num : range nums { if (num diff) 0 { res[0] ^ num } else { res[1] ^ num } } return res从 136 → 137 → 260 的递进可以看出异或与位运算不只是某一道题的技巧而是处理成对抵消、单点幸存类问题的一整套方法论出现两次靠异或抵消出现三次靠位计数状态机出现两个幸存者靠最低置位分组。复杂度与正确性总结维度结论依据时间复杂度O(n)单层循环遍历数组一次循环体为常数次位运算空间复杂度O(1)仅一个int累积变量无哈希表、无额外切片正确性依赖异或的交换律、结合律与x ^ x 0、x ^ 0 x实现源码 与 测试用例 共同验证从源码结构看本题的题解文档0136.Single-Number.md、Go 实现与测试文件三位一体共同构成 LeetCode-Go 仓库中文档 实现 测试的标准组织模式读者可以沿着 leetcode 目录 下的同名题目目录逐一对照研读。一句话总结136 的本质是全员异或、成对抵消、余者即答案——以 O(n) 时间、O(1) 空间完成一次精妙的位运算之旅而这一思路正是后续 137、260 等位运算难题的基石。【免费下载链接】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 题解 0136：利用异或运算求解 Single Number（只出现一次的数字）
LeetCode-Go 题解 0136利用异或运算求解 Single Number只出现一次的数字【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 0136.Single-Number 题解文档 为核心讲解 LeetCode 136「只出现一次的数字」这道经典位运算题目在 LeetCode-Go 仓库中的完整解法。你将掌握异或运算的三大核心性质理解其余元素均出现两次、仅一个元素出现一次这一约束如何天然导向 XOR 解法并看到该思路在仓库中 Single Number II137 与 Single Number III260 上的延伸应用。读完本文你既能写出时间复杂度 O(n)、空间复杂度 O(1) 的 Go 实现也能从源码与测试层面验证其正确性。题目描述给定一个非空整数数组其中每个元素都出现两次除了某个元素只出现一次。找出那个只出现一次的元素。注意算法应当具备线性时间复杂度linear runtime complexity能否不使用额外内存extra memory实现示例 1Input: [2,2,1] Output: 1示例 2Input: [4,1,2,1,2] Output: 4题目小结给定一个非空整数数组除一个元素只出现一次外其余每个元素均出现两次找出那个只出现一次的元素要求算法时间复杂度为线性且不使用额外辅助空间。解题思路从出现两次到异或抵消为什么题目强调其余元素均出现两次题目明确要求不使用辅助空间、只允许线性时间遍历这直接排除了两套常见但不符合约束的方案哈希表计数法遍历数组统计每个数字出现次数再找出现次数为 1 的数字。虽然时间复杂度是 O(n)但需要 O(n) 的额外空间违反空间约束双重循环暴力查找对每个元素再遍历一次数组确认是否唯一虽然空间是 O(1)但时间复杂度为 O(n²)违反时间约束。于是需要一种既不借助容器、又能在线性时间内一次遍历完成筛选的手段。此时题目特意强调一个数字出现一次其他都出现两次这个两次就是解题的钥匙——它恰好对应异或运算XOR的核心性质任何一个数字异或它自己结果都等于 0即 x ^ x 0。由此可以得到三个推论x ^ 0 x任何数与 0 异或保持不变x ^ x 0任何数与自身异或结果为 0异或满足交换律与结合律a ^ b ^ a (a ^ a) ^ b 0 ^ b b运算顺序不影响最终结果。核心思路从头到尾依次异或如果我们从头到尾依次异或数组中的每一个数字那么所有出现两次的数字都会两两抵消为 0最终剩下的结果恰好就是那个只出现一次的数字。以示例 2 的[4,1,2,1,2]为例逐步推演4 ^ 1 ^ 2 ^ 1 ^ 2 4 ^ (1 ^ 1) ^ (2 ^ 2) // 结合律成对的 1 与成对的 2 各自抵消 4 ^ 0 ^ 0 4正因为异或的交换律和结合律成对出现的数字无论相隔多远都会在异或链中相互抵消最终result中只保留唯一的那个数字。利用的性质就是 x ^ x 0。源码实现单次遍历、常数空间仓库中本题的 Go 实现位于 136. Single Number.go核心代码与原题解文档一致package leetcode func singleNumber(nums []int) int { result : 0 for i : 0; i len(nums); i { result ^ nums[i] } return result }代码逻辑非常紧凑用result : 0初始化累积值利用x ^ 0 x保证首轮异或不改变结果单层循环遍历整个数组每次执行result ^ nums[i]循环结束后成对出现的数字全部抵消result即为只出现一次的那个数字整个过程只使用了一个int变量额外空间为O(1)单层循环遍历 n 个元素时间复杂度为O(n)完全满足题目的双重约束。测试验证表驱动用例印证正确性仓库为本题编写了配套测试 136. Single Number_test.go采用标准的表驱动table-driven测试结构用para136承载输入数组、ans136承载期望输出再通过question136结构体组合两者。测试用例完整覆盖了题面给出的两个示例输入数组期望输出[2,2,1]1[4,1,2,1,2]4测试主体遍历用例并调用singleNumber(p.s)与期望值比对同时打印【input】/【output】便于人工核对for _, q : range qs { _, p : q.ans136, q.para136 fmt.Printf(【input】:%v 【output】:%v\n, p, singleNumber(p.s)) }在仓库根目录执行go test相关命令即可运行验证例如go test -v -run Test_Problem136 ./leetcode/0136.Single-Number/...这两个用例虽少但分别覆盖了单元素成对抵消后剩首元素[2,2,1]与目标元素位于数组中间[4,1,2,1,2]两种典型排布足以验证异或解法的正确性。同族问题延伸从出现两次到出现三次与出现两个单数掌握了 136 的异或思路后可以顺藤摸瓜在仓库中探索两个同族问题它们体现了同一数学工具在不同约束下的演进137. Single Number II每个元素出现三次仓库 137. Single Number II.go 处理的是除一个元素外其余元素均出现三次的版本。此时简单的全员异或不再奏效x ^ x ^ x x而非 0需要升级为逐位统计 状态机的思路func singleNumberII(nums []int) int { ones, twos : 0, 0 for i : 0; i len(nums); i { ones (ones ^ nums[i]) ^twos twos (twos ^ nums[i]) ^ones } return ones }ones记录出现 1 次的位、twos记录出现 2 次的位出现 3 次时两个标志位同时清零最终ones即只出现一次的数字。值得注意的是该文件还附带了两套每个元素出现 5 次的拓展实现展示了如何把有限状态机推广到任意出现次数很适合作为进阶阅读。260. Single Number III两个只出现一次的数字仓库 260. Single Number III.go 处理的是除两个元素外其余元素均出现两次的版本。思路是分两步走先全员异或得到diff a ^ b两个目标数字的异或结果非零取diff的最低置位diff -diff作为划分依据a与b在这一位上必然不同按该位是否为 0 把数组分成两组分别异或两组各自剩下的就是a与bdiff -diff // Get its last set bit (lsb) res : []int{0, 0} for _, num : range nums { if (num diff) 0 { res[0] ^ num } else { res[1] ^ num } } return res从 136 → 137 → 260 的递进可以看出异或与位运算不只是某一道题的技巧而是处理成对抵消、单点幸存类问题的一整套方法论出现两次靠异或抵消出现三次靠位计数状态机出现两个幸存者靠最低置位分组。复杂度与正确性总结维度结论依据时间复杂度O(n)单层循环遍历数组一次循环体为常数次位运算空间复杂度O(1)仅一个int累积变量无哈希表、无额外切片正确性依赖异或的交换律、结合律与x ^ x 0、x ^ 0 x实现源码 与 测试用例 共同验证从源码结构看本题的题解文档0136.Single-Number.md、Go 实现与测试文件三位一体共同构成 LeetCode-Go 仓库中文档 实现 测试的标准组织模式读者可以沿着 leetcode 目录 下的同名题目目录逐一对照研读。一句话总结136 的本质是全员异或、成对抵消、余者即答案——以 O(n) 时间、O(1) 空间完成一次精妙的位运算之旅而这一思路正是后续 137、260 等位运算难题的基石。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考