尧图网站建设 
LeetCode-Go 题解137. Single Number II —— 三进制状态机位运算消灭出现三次的元素【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 137Single Number II展开在一个非空整数数组中每个元素恰好出现三次、只有一个元素只出现一次要求在线性时间内且不使用额外辅助空间找出它。文章以 leetcode/0137.Single-Number-II/README.md 为核心骨架结合本仓库的 Go 实现源码 与 单元测试完整推导基于三进制计数器的位运算状态机解法并延伸讲解每个元素出现 5 次的推广版本。读完后你将掌握一类位运算计数器的通用建模方法并理解 Go 语言中^、一元^等位运算符在状态机实现中的具体作用。一、题目回顾题目原文摘要给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现三次找出那个只出现一次的元素。额外约束Note算法应具有线性时间复杂度linear runtime complexity能否不使用额外内存without using extra memory实现示例 1Input: [2,2,3,2] Output: 3示例 2Input: [0,1,0,1,0,1,99] Output: 99也就是说题目希望我们突破 HashMap 计数这类 O(n) 空间方案仅用若干个整型变量完成统计——这正是位运算的用武之地。二、从第 136 题说起异或为什么能消除出现两次137 是 第 136 题 Single Number 的加强版。136 题中每个元素出现两次、只有一个出现一次其解法只依赖异或的一个性质任何一个数字异或它自己都等于 0即x ^ x 0。从头到尾把所有数字异或一遍出现两次的数字两两抵消最终结果就是那个只出现一次的数字。仓库中 136 题的 Go 实现 只有短短几行func singleNumber(nums []int) int { result : 0 for i : 0; i len(nums); i { result ^ nums[i] } return result }异或的自反消去本质上是模 2 加法某一位上 1 出现偶数次就被清零。那么当元素出现三次时我们需要的是一种模 3 加法某一位上 1 出现 3 次就归零清除。这就是 137 题的核心难点也是本题与 136 题在思路上分道扬镳的地方。顺带一提同系列的 260. Single Number III 处理的是两个数各出现一次、其余出现两次的场景思路是用整体异或结果的最低位 1lsb把数组分成两半再分别异或仓库实现见 260. Single Number III.go。三题连起来看就是一条从模 2 计数到模 3 计数再到分组异或的完整位运算训练链。三、核心思路用两个变量模拟三进制状态机原文档明确指出本题需要定义00、10、01 三个状态仿造**三进制00、01、10**来统计每个位上 1 出现的次数。先看单个二进制位。我们需要一个能数到 3 的计数器数满 3 自动归零0 次 → 状态001 次 → 状态012 次 → 状态103 次 → 回到00被消除由于单个变量只有 0/1 两种取值数到 3 至少需要两个变量。原文档将这两个变量命名为ones和twosones记录遍历过程中每个位上出现 1 的次数为 1低位twos记录遍历过程中每个位上出现 1 的次数为 2高位进位。ones的更新意图原文档将ones与A[i]进行异或若某一位上历史统计ones已是 1、A[i]中又是 1说明累计出现 2 次需要进位到twos若两者分别为 0、1则把这次出现累加进ones最后还要与^twos做与运算这是为了做到三进制——出现 3 次就清零。例如ones x时twos 0而当twos x时ones应为 0。twos的更新与上述描述对称twos记录每位上 1 出现 2 次的个数同样与A[i]异或后做进位/清零处理。3.1 状态转移真值表ones → ones原文档给出第一步的状态转移表其中ones是更新后的ones(twos, ones)xi(twos, ones)ones000000001011010011011100100100101000观察可得更新式第一步ones (ones ^ nums[i]) ^twosones ^ nums[i]负责在twos 0时做正常的模 2 累加 ^twos负责在已经进位到twos累计 2 次时把ones清零为第三次出现后的归零铺路。3.2 状态转移真值表twos → twos第二步更新twos这一步需要用到前一步更新后的ones即ones保证二者不会同时为 1(twos, ones)xitwos000001100100001110011010观察可得更新式第二步twos (twos ^ nums[i]) ^ones这里使用更新后的ones而非旧值是保证状态机在每一位上严格处于00 / 01 / 10三种合法状态之一的关键ones与twos同一位永远不会同时为 1。四、Go 实现与位运算符说明将上面两步写成循环即仓库 137. Single Number II.go 中的主解法package leetcode 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中因此直接return ones。4.1 Go 与 Java 位运算符的差异原文档重点原文档特别强调了两点使用 Go 编写时极易踩坑Go 中^表示 AND NOTX ^ Y的含义是——保留X中与Y相异的位将相同的位清零。它等价于X (^Y)这正是状态转移式里清零操作的语义来源。Go 没有 Java 的~运算符Java 中~表示按位取反Go 中这一功能由一元^承担例如^0001 0100 1110 1011。因此(ones ^ nums[i]) ^twos翻译成 Java 风格就是(ones ^ nums[i]) ~twos。理解这层对应关系代码在不同语言间迁移时就不会写错。4.2 为什么满足不使用额外空间整个算法只使用了ones、twos两个额外整型变量与数组长度无关空间复杂度为O(1)单次遍历数组、每轮常数次位运算时间复杂度为O(n)。两项指标都严格满足题目 Note 的要求。五、测试验证仓库测试用例如何佐证仓库为本题提供了完整测试137. Single Number II_test.go覆盖了原文档中的两个官方示例qs : []question137{ { para137{[]int{2, 2, 3, 2}}, ans137{3}, }, { para137{[]int{0, 1, 0, 1, 0, 1, 99}}, ans137{99}, }, }测试框架沿用本仓库统一的question/para/ans表驱动风格para137封装输入数组sans137封装期望答案one。主测试函数不仅调用singleNumberII验证主解法还会顺带调用两个出现 5 次的拓展解法singleNumberIIIII与singleNumberIIIII1见下文确保主解与推广解对相同输入输出一致。在本地可直接运行仓库根目录的gotest.sh或执行go test ./leetcode/0137.Single-Number-II/ -v复现这些用例。六、一题多吃扩展到每个元素出现 5 次原文档明确指出本题思路可以继续扩展——若数组中每个元素都出现 5 次、只有一个元素出现 1 次做法仍是模拟一个五进制计数器数满 5 次自动消除。仓库 137. Single Number II.go 中给出了两种解法。6.1 解法一三个变量 na / nb / nc// 解法一 func singleNumberIIIII(nums []int) int { na, nb, nc : 0, 0, 0 for i : 0; i len(nums); i { nb nb ^ (nums[i] na) na (na ^ nums[i]) ^nc nc nc ^ (nums[i] ^na ^nb) } return na ^nb ^nc }思路延续三进制版数到 5 需要三个二进制位可表示 07这里用na、nb、nc三个变量组合成五进制状态机。前两行与 137 主解结构高度相似第三行nc负责在更高位计数最终结果通过na ^nb ^nc从状态中提取只出现一次的元素。可以推断若继续推广到出现 k 次需要约⌈log₂(k1)⌉个变量本质都是用足够多的位来构造一个能数到 k 的计数器。6.2 解法二ones / twos / threes 三变量// 解法二 func singleNumberIIIII1(nums []int) int { twos, threes, ones : 0xffffffff, 0xffffffff, 0 for i : 0; i len(nums); i { threes threes ^ (nums[i] twos) twos (twos ^ nums[i]) ^ones ones ones ^ (nums[i] ^twos ^threes) } return ones }解法二将三个变量分别命名为ones、twos、threes其中twos与threes初始化为0xffffffff即 32 位全 1等价于清零掩码的取反基准。每轮更新顺序为threes → twos → ones层层进位最终只出现一次的数同样落在ones中。两种解法的变量命名风格略有差异na/nb/nc与ones/twos/threes但都遵守低位先更新、高位引用低位最新值的同一状态机纪律。原文档还附带了这两个版本的源码与仓库实现一一对应读者可直接复制运行对比。七、总结137 题是位运算状态机的一类经典代表核心要点可归纳为问题本质把按次数消除从模 2异或推广到模 3需要不止一个变量来记录每位上 1 出现的次数状态设计用(twos, ones)两个变量编码00 / 01 / 10三态出现 3 次自动归零转移方程ones (ones ^ nums[i]) ^twos、twos (twos ^ nums[i]) ^ones两条式子交替更新、互相约束Go 语言要点^是 AND NOT一元^是按位取反二者组合实现了状态机中的清零操作可推广性同一思路可扩展到出现 5 次乃至一般 k 次只需增加计数变量与进位层次。仓库中的 题解文档、实现源码 与 测试用例 三者互为印证是理解与复习此题的最佳材料结合 136 题 与 260 题 一起阅读可以完整打通出现 2 次 / 3 次 / 两个 1 次的位运算系列题型。【免费下载链接】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 题解：137. Single Number II —— 三进制状态机位运算消灭出现三次的元素
LeetCode-Go 题解137. Single Number II —— 三进制状态机位运算消灭出现三次的元素【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 137Single Number II展开在一个非空整数数组中每个元素恰好出现三次、只有一个元素只出现一次要求在线性时间内且不使用额外辅助空间找出它。文章以 leetcode/0137.Single-Number-II/README.md 为核心骨架结合本仓库的 Go 实现源码 与 单元测试完整推导基于三进制计数器的位运算状态机解法并延伸讲解每个元素出现 5 次的推广版本。读完后你将掌握一类位运算计数器的通用建模方法并理解 Go 语言中^、一元^等位运算符在状态机实现中的具体作用。一、题目回顾题目原文摘要给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现三次找出那个只出现一次的元素。额外约束Note算法应具有线性时间复杂度linear runtime complexity能否不使用额外内存without using extra memory实现示例 1Input: [2,2,3,2] Output: 3示例 2Input: [0,1,0,1,0,1,99] Output: 99也就是说题目希望我们突破 HashMap 计数这类 O(n) 空间方案仅用若干个整型变量完成统计——这正是位运算的用武之地。二、从第 136 题说起异或为什么能消除出现两次137 是 第 136 题 Single Number 的加强版。136 题中每个元素出现两次、只有一个出现一次其解法只依赖异或的一个性质任何一个数字异或它自己都等于 0即x ^ x 0。从头到尾把所有数字异或一遍出现两次的数字两两抵消最终结果就是那个只出现一次的数字。仓库中 136 题的 Go 实现 只有短短几行func singleNumber(nums []int) int { result : 0 for i : 0; i len(nums); i { result ^ nums[i] } return result }异或的自反消去本质上是模 2 加法某一位上 1 出现偶数次就被清零。那么当元素出现三次时我们需要的是一种模 3 加法某一位上 1 出现 3 次就归零清除。这就是 137 题的核心难点也是本题与 136 题在思路上分道扬镳的地方。顺带一提同系列的 260. Single Number III 处理的是两个数各出现一次、其余出现两次的场景思路是用整体异或结果的最低位 1lsb把数组分成两半再分别异或仓库实现见 260. Single Number III.go。三题连起来看就是一条从模 2 计数到模 3 计数再到分组异或的完整位运算训练链。三、核心思路用两个变量模拟三进制状态机原文档明确指出本题需要定义00、10、01 三个状态仿造**三进制00、01、10**来统计每个位上 1 出现的次数。先看单个二进制位。我们需要一个能数到 3 的计数器数满 3 自动归零0 次 → 状态001 次 → 状态012 次 → 状态103 次 → 回到00被消除由于单个变量只有 0/1 两种取值数到 3 至少需要两个变量。原文档将这两个变量命名为ones和twosones记录遍历过程中每个位上出现 1 的次数为 1低位twos记录遍历过程中每个位上出现 1 的次数为 2高位进位。ones的更新意图原文档将ones与A[i]进行异或若某一位上历史统计ones已是 1、A[i]中又是 1说明累计出现 2 次需要进位到twos若两者分别为 0、1则把这次出现累加进ones最后还要与^twos做与运算这是为了做到三进制——出现 3 次就清零。例如ones x时twos 0而当twos x时ones应为 0。twos的更新与上述描述对称twos记录每位上 1 出现 2 次的个数同样与A[i]异或后做进位/清零处理。3.1 状态转移真值表ones → ones原文档给出第一步的状态转移表其中ones是更新后的ones(twos, ones)xi(twos, ones)ones000000001011010011011100100100101000观察可得更新式第一步ones (ones ^ nums[i]) ^twosones ^ nums[i]负责在twos 0时做正常的模 2 累加 ^twos负责在已经进位到twos累计 2 次时把ones清零为第三次出现后的归零铺路。3.2 状态转移真值表twos → twos第二步更新twos这一步需要用到前一步更新后的ones即ones保证二者不会同时为 1(twos, ones)xitwos000001100100001110011010观察可得更新式第二步twos (twos ^ nums[i]) ^ones这里使用更新后的ones而非旧值是保证状态机在每一位上严格处于00 / 01 / 10三种合法状态之一的关键ones与twos同一位永远不会同时为 1。四、Go 实现与位运算符说明将上面两步写成循环即仓库 137. Single Number II.go 中的主解法package leetcode 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中因此直接return ones。4.1 Go 与 Java 位运算符的差异原文档重点原文档特别强调了两点使用 Go 编写时极易踩坑Go 中^表示 AND NOTX ^ Y的含义是——保留X中与Y相异的位将相同的位清零。它等价于X (^Y)这正是状态转移式里清零操作的语义来源。Go 没有 Java 的~运算符Java 中~表示按位取反Go 中这一功能由一元^承担例如^0001 0100 1110 1011。因此(ones ^ nums[i]) ^twos翻译成 Java 风格就是(ones ^ nums[i]) ~twos。理解这层对应关系代码在不同语言间迁移时就不会写错。4.2 为什么满足不使用额外空间整个算法只使用了ones、twos两个额外整型变量与数组长度无关空间复杂度为O(1)单次遍历数组、每轮常数次位运算时间复杂度为O(n)。两项指标都严格满足题目 Note 的要求。五、测试验证仓库测试用例如何佐证仓库为本题提供了完整测试137. Single Number II_test.go覆盖了原文档中的两个官方示例qs : []question137{ { para137{[]int{2, 2, 3, 2}}, ans137{3}, }, { para137{[]int{0, 1, 0, 1, 0, 1, 99}}, ans137{99}, }, }测试框架沿用本仓库统一的question/para/ans表驱动风格para137封装输入数组sans137封装期望答案one。主测试函数不仅调用singleNumberII验证主解法还会顺带调用两个出现 5 次的拓展解法singleNumberIIIII与singleNumberIIIII1见下文确保主解与推广解对相同输入输出一致。在本地可直接运行仓库根目录的gotest.sh或执行go test ./leetcode/0137.Single-Number-II/ -v复现这些用例。六、一题多吃扩展到每个元素出现 5 次原文档明确指出本题思路可以继续扩展——若数组中每个元素都出现 5 次、只有一个元素出现 1 次做法仍是模拟一个五进制计数器数满 5 次自动消除。仓库 137. Single Number II.go 中给出了两种解法。6.1 解法一三个变量 na / nb / nc// 解法一 func singleNumberIIIII(nums []int) int { na, nb, nc : 0, 0, 0 for i : 0; i len(nums); i { nb nb ^ (nums[i] na) na (na ^ nums[i]) ^nc nc nc ^ (nums[i] ^na ^nb) } return na ^nb ^nc }思路延续三进制版数到 5 需要三个二进制位可表示 07这里用na、nb、nc三个变量组合成五进制状态机。前两行与 137 主解结构高度相似第三行nc负责在更高位计数最终结果通过na ^nb ^nc从状态中提取只出现一次的元素。可以推断若继续推广到出现 k 次需要约⌈log₂(k1)⌉个变量本质都是用足够多的位来构造一个能数到 k 的计数器。6.2 解法二ones / twos / threes 三变量// 解法二 func singleNumberIIIII1(nums []int) int { twos, threes, ones : 0xffffffff, 0xffffffff, 0 for i : 0; i len(nums); i { threes threes ^ (nums[i] twos) twos (twos ^ nums[i]) ^ones ones ones ^ (nums[i] ^twos ^threes) } return ones }解法二将三个变量分别命名为ones、twos、threes其中twos与threes初始化为0xffffffff即 32 位全 1等价于清零掩码的取反基准。每轮更新顺序为threes → twos → ones层层进位最终只出现一次的数同样落在ones中。两种解法的变量命名风格略有差异na/nb/nc与ones/twos/threes但都遵守低位先更新、高位引用低位最新值的同一状态机纪律。原文档还附带了这两个版本的源码与仓库实现一一对应读者可直接复制运行对比。七、总结137 题是位运算状态机的一类经典代表核心要点可归纳为问题本质把按次数消除从模 2异或推广到模 3需要不止一个变量来记录每位上 1 出现的次数状态设计用(twos, ones)两个变量编码00 / 01 / 10三态出现 3 次自动归零转移方程ones (ones ^ nums[i]) ^twos、twos (twos ^ nums[i]) ^ones两条式子交替更新、互相约束Go 语言要点^是 AND NOT一元^是按位取反二者组合实现了状态机中的清零操作可推广性同一思路可扩展到出现 5 次乃至一般 k 次只需增加计数变量与进位层次。仓库中的 题解文档、实现源码 与 测试用例 三者互为印证是理解与复习此题的最佳材料结合 136 题 与 260 题 一起阅读可以完整打通出现 2 次 / 3 次 / 两个 1 次的位运算系列题型。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考