教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载本篇基于 YCBlogs 仓库 leetcode/01.数组/08.数组中只出现一次的数字.md 展开针对经典面试题“找出数组中只出现一次的数字”给出完整解题路径从 HashMap 计数、HashSet 增删到异或位运算三种方案的完整 Java 实现、复杂度对比与原理推导。读完后你将掌握“出现偶数次的元素互相抵消”这一位运算思想并能将其迁移到更复杂的变体问题上。一、题目要求原文档给出的问题描述如下给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗题目的关键约束有两点数组非空且唯一“落单”的元素只有一个其余元素恰好出现两次算法要求线性时间复杂度 O(n)并进一步追问能否做到不使用额外空间 O(1)。这两个追问实际上决定了三种解法的分层第一种方案满足线性时间但空间为 O(n)第二种方案同样 O(n) 空间但实现更简洁第三种异或方案才真正回答“能否 O(1) 空间”——能。二、问题分析用示例理解题意原文档给出两个示例示例 1输入: [2,2,1] 输出: 1示例 2输入: [4,1,2,1,2] 输出: 4以示例 2 为例元素 1 出现两次、2 出现两次、4 只出现一次因此答案是 4。这个“成对出现 唯一落单”的数据特征是所有解法的基础只要有一种机制能让“出现两次的元素互相抵消、最后只剩落单者”问题就迎刃而解。HashMap 靠“计数到 2 即淘汰”实现HashSet 靠“二次出现即移除”实现异或则靠位运算的x ^ x 0天然实现。三、方案一HashMap 计数法原文档的第一个思路把所有值作为 Map 的 key出现次数作为 value最后次数为 1 的就是那个单个值。代码完整继承自原文档/** * 我能想到的第一个方法就是把所有的值当成 Map 的key出现的次数当成value * 最后次数为 1 的就是那个单个的 */ RequiresApi(api Build.VERSION_CODES.N) public int singleNumber(int[] nums) { MapInteger, Integer map new HashMap(); for (int num : nums) { if (!map.containsKey(num)) { map.put(num, 1); } else { map.put(num, map.get(num) 1); } } return map.entrySet().stream().filter(r - r.getValue() 1).findFirst().get().getKey(); }逐段解析第一层循环做频率统计遍历数组元素首次出现时put(num, 1)再次出现时自增为 2。遍历结束后只有落单元素的计数停留在 1其余全部为 2。stream 过滤取结果filter(r - r.getValue() 1)筛出计数为 1 的键值对。findFirst().get()能安全取值是因为题目保证了唯一解一定存在。RequiresApi(api Build.VERSION_CODES.N)注解的含义原文档运行在 Android 工程中map.entrySet().stream()这条集合 Stream API 需要 API 24Android N才可用因此在 Android 低版本环境下需要该注解声明如果放在纯 Java 8 桌面工程中则无需此注解可直接使用 stream。复杂度分析结合仓库 leetcode/00.导向/03.时间复杂度.md 中“只关注循环执行次数最多的一段代码”的方法时间复杂度 O(n)统计循环执行 n 次stream 过滤最坏再遍历一次 map 的 n 个键值对量级仍为 O(n)符合题目“线性时间”要求空间复杂度 O(n)最坏情况下所有元素互不相同前缀阶段map 需要保存接近 n 个键值对无法满足“不使用额外空间”的追问。这是“计数问题”的通用第一反应正确但非最优适合作为思维起点。四、方案二HashSet 增删法加一遍、删一遍原文档的第二个思路看到重复元素本能地想到 Set——把出现两次的数字先添加到 Set 里面然后再移除掉最后剩下的就是单个的值。完整代码/** * 看到重复元素本能的想到 Set,可以考虑把出现两次的数字先添加到 Set 里面然后再移除掉 * 最后剩下一个就是单个的值。 */ public int singleNumber1(int[] nums) { SetInteger set new HashSet(); for (int num : nums) { if (!set.remove(num)) { set.add(num); } } return set.iterator().next(); }这段代码的精髓在if (!set.remove(num))这一行HashSet.remove(e)返回boolean移除成功返回 true元素本就不存在返回 false因此逻辑是先尝试删除删掉了说明这是第二次出现什么都不做没删掉说明这是第一次出现就加入集合遍历结束后Set 里只剩落单元素iterator().next()直接取出。相比 HashMap 方案HashSet 方案有两个优点一是无需显式维护计数Set 的存在性天然等价于“出现奇数次”二是空间上只存元素本身而非键值对常数更小。但其时间复杂度仍为 O(n)、空间复杂度仍为 O(n)见 leetcode/00.导向/04.空间复杂度.md 中“空间复杂度表示算法存储空间与数据规模的增长关系”的定义此处随 n 线性增长的正是 Set 本身。理解 Set 方案的机制时可延伸阅读仓库中 leetcode/08.Hash/08.Java中Hash应用.md 关于散列函数、hash 冲突与链地址法的内容——HashSet底层依赖HashMap其增删查的均摊 O(1) 表现正是建立在哈希表这一结构之上。五、方案三异或位运算法最优解O(1) 空间原文档的第三个思路是本题的正解也是唯一满足“线性时间 无额外空间”的方案/** * 异或(^) 运算法则为0⊕001⊕010⊕111⊕10同为0异为1 * 除了其中一个数字是一次外其他的都是两次相同的值异或结果为0用0异或所有的值 * 最终结果就是那个单个的值。 */ public int singleNumber2(int[] nums) { int r 0; for (int num : nums) { r ^ num; } return r; }5.1 异或运算的三条关键性质异或XOR^是逐位进行的按位运算0⊕00、1⊕01、0⊕11、1⊕10即“同 0 异 1”。由此可推出三条对本题至关重要的性质交换律与结合律a ^ b ^ c与运算顺序无关因此无论数组元素以什么顺序出现累加异或的结果都一样自反性x ^ x 0任何数异或自身为 0这正是“出现两次的元素互相抵消”的数学保证单位元x ^ 0 x0 是异或的单位元因此可以令累加器初始值为 0逐位“吸收”数组元素而不改变最终结果。5.2 以 [4,1,2,1,2] 逐步模拟按r ^ num顺序执行步骤当前 num计算r十进制r二进制初始——00000140 ^ 440100214 ^ 150101325 ^ 270111417 ^ 160110526 ^ 240100最终 r 4与题目示例 2 的输出一致。注意第 2 步与第 4 步元素 1 第一次进入累加器0101第二次出现时7 ^ 1 6又把它“消掉”了0110两个 1 的贡献恰好归零。用 [2,2,1] 同样验证0^22 → 2^20 → 0^11结果为 1。5.3 为什么“抵消”总是成立成对出现的每个元素 x 会贡献两次^ x根据结合律可将其相邻看待... ^ x ^ x ^ ... ... ^ (x ^ x) ^ ... ... ^ 0 ^ ...即该元素对最终结果毫无影响剩下的唯一元素 y 只贡献一次最终0 ^ y y。因此无论落单元素在数组什么位置结果都等于它本身。复杂度单次遍历每个元素只做一次异或操作时间复杂度 O(n)除累加器r外不申请任何与 n 相关的存储空间复杂度 O(1)完美回答了题目的追问。六、三种方案对比小结方案核心数据结构/机制时间复杂度空间复杂度特点HashMap 计数计数 流过滤O(n)O(n)思路最直白通用性强可放宽到“出现三次”等变体HashSet 增删remove返回值判断奇偶O(n)O(n)代码最简洁空间常数更小异或累加x ^ x 0位运算O(n)O(1)本题最优解依赖“恰好出现两次”的题设选型建议面试先给出异或解法点明最优复杂度再说明 Hash 方案作为“允许 O(n) 空间时的通用兜底”工程上若题设放宽为“其余元素出现 k 次k 为奇数次以外的任意值”HashMap 计数法仍是更稳妥的通用手段。七、进阶延伸两个只出现一次的数字仓库中紧接的 leetcode/01.数组/21.数组中只出现一次的数字.md 给出了本题的经典变体一个整型数组里除了两个数字之外其他数字都出现了两次要求 O(n) 时间、O(1) 空间找出这两个数字示例输入{2, 4, 3, 6, 3, 2, 5}输出 4 和 6。其解法正是建立在本文异或思想之上的递进先把整个数组异或得到a ^ b两个落单者的异或结果成对元素全部抵消由于a ≠ b该结果二进制中必有 1 位取其第一个为 1 的位作为分组标准把数组拆成两组——出现了两次的相同数字任意对应位相同必然被分进同一组于是每组都退化为“唯一单数”问题再各做一次异或即可。原文档中的实现findFirstBit1用无符号右移逐位探测、isBit1判断分组位完整保留了这一分组-再异或的两阶段流程值得对照本文方案三一起研读以掌握“异或抵消”思想从一题到变体的迁移方法。八、仓库内相关阅读leetcode/01.数组/08.数组中只出现一次的数字.md本文主体来源三种解法原始代码leetcode/01.数组/21.数组中只出现一次的数字.md两个落单数字的分组异或进阶解leetcode/00.导向/03.时间复杂度.md 与 leetcode/00.导向/04.空间复杂度.md复杂度分析方法的基础铺垫leetcode/08.Hash/08.Java中Hash应用.mdHashMap/HashSet 底层散列机制的背景知识。赞分享教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载相关推荐Rufus 4.15 一步做出可启动U盘教程从格式化、哈希校验到装完 Windows 11Rufus 4.15 一步做出可启动U盘教程从格式化、哈希校验到装完 Windows 11 想制作启动U盘Rufus 可以一步到位。这款免安装小工具把格式化桌面应用开发工具algorithm-base 图解算法LeetCode 260 只出现一次的数字 III —— HashSet 成对消去与位运算分组异或全解algorithm base 图解算法LeetCode 260 只出现一次的数字 III —— HashSet 成对消去与位运算分组异或全解 本文是 algo文档教程知识库CS-Notes 剑指 Offer 56用异或位运算找出数组中只出现一次的两个数字CS Notes 剑指 Offer 56用异或位运算找出数组中只出现一次的两个数字 本篇围绕 CS Notes 仓库《剑指 Offer 题解》中的 第 56知识库文档教程上一篇Panda CSS 跨文件解析架构正向折叠、反向查询与 Watch 失效的设计取舍下一篇windows-kernel-exploits 仓库 MS15-076CVE-2015-2370Windows RPC 权限提升Trebuchet 任意位置文件复制利用全解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考