简单提示给你一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。示例 1 输入nums [2,2,1]输出1示例 2 输入nums [4,1,2,1,2]输出4示例 3 输入nums [1]输出1提示1 nums.length 3 * 104-3 * 104 nums[i] 3 * 104除了某个元素只出现一次以外其余每个元素均出现两次。 核心笔记只出现一次的数字 (Single Number - XOR)1. 核心思想 (一句话总结)“消消乐魔法异或运算就像‘对对碰’两个相同的数字相遇会变成 0相互抵消最后剩下的那个就是落单的数字。”性质 AN ^ N 0(自己异或自己归零)。性质 BN ^ 0 N(任何数异或 0保持不变)。性质 C满足交换律和结合律 (顺序无所谓a ^ b ^ c等于a ^ c ^ b)。结论a ^ b ^ a ^ c ^ b(a^a) ^ (b^b) ^ c0 ^ 0 ^ cc。2. 算法流程 (Iterative XOR)初始化 (Init)ans 0。因为 0 是异或的单位元就像加法里的 0乘法里的 1它不会改变计算结果。遍历 (Loop)遍历数组中的每一个数x。执行ans ans ^ x。在这个过程中所有成对出现的数字无论它们相隔多远最终都会在异或的数学层面上“相遇”并抵消成 0。结果 (Result)循环结束后ans里剩下的就是那个唯一的、没有被抵消的数字。 代码回忆清单// 题目LC 136. Single Number class Solution { public int singleNumber(int[] nums) { // 1. 初始化为 0 // 0 ^ x x保证第一个数进去后保持原样 int ans 0; // 2. 遍历所有数字 for (int x : nums) { // 3. 异或累加 (消消乐) // 相同的数字会在过程中互相抵消 ans ^ x; } // 4. 返回幸存者 return ans; } }⚡ 快速复习 CheckList (易错点)[ ]为什么不需要排序因为异或满足交换律。[4, 1, 2, 1, 2]的计算顺序虽然是4^1^2^1^2但数学上等价于4 ^ (1^1) ^ (2^2)。[ ]如果用 HashSet 呢也可以。Set存第一次遇到的删第二次遇到的。最后剩在 Set 里的就是结果。但是 Set 需要 的空间题目进阶要求 空间所以必须用异或。[ ]通用性这个解法只适用于“其他数字都出现偶数次(2次, 4次...)”的情况。如果其他数字出现 3 次需要用位统计法 (LC 137)。️ 数字演练nums [4, 1, 2, 1, 2]初始:ans 0。x 4:ans 0 ^ 4 4。(目前落单的是 4)x 1:ans 4 ^ 1。 (结果是 5二进制 100^001101。暂时看不出意义继续)x 2:ans 4 ^ 1 ^ 2。x 1(关键):ans 4 ^ 1 ^ 2 ^ 1。利用交换律调整视角4 ^ 2 ^ (1 ^ 1)-4 ^ 2 ^ 0。1 被消掉了x 2(关键):ans 4 ^ 2 ^ 0 ^ 2。调整视角4 ^ (2 ^ 2) ^ 0-4 ^ 0 ^ 0。2 被消掉了最终结果:4。
136. 只出现一次的数字
发布时间：2026/6/10 9:11:57
简单提示给你一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。示例 1 输入nums [2,2,1]输出1示例 2 输入nums [4,1,2,1,2]输出4示例 3 输入nums [1]输出1提示1 nums.length 3 * 104-3 * 104 nums[i] 3 * 104除了某个元素只出现一次以外其余每个元素均出现两次。 核心笔记只出现一次的数字 (Single Number - XOR)1. 核心思想 (一句话总结)“消消乐魔法异或运算就像‘对对碰’两个相同的数字相遇会变成 0相互抵消最后剩下的那个就是落单的数字。”性质 AN ^ N 0(自己异或自己归零)。性质 BN ^ 0 N(任何数异或 0保持不变)。性质 C满足交换律和结合律 (顺序无所谓a ^ b ^ c等于a ^ c ^ b)。结论a ^ b ^ a ^ c ^ b(a^a) ^ (b^b) ^ c0 ^ 0 ^ cc。2. 算法流程 (Iterative XOR)初始化 (Init)ans 0。因为 0 是异或的单位元就像加法里的 0乘法里的 1它不会改变计算结果。遍历 (Loop)遍历数组中的每一个数x。执行ans ans ^ x。在这个过程中所有成对出现的数字无论它们相隔多远最终都会在异或的数学层面上“相遇”并抵消成 0。结果 (Result)循环结束后ans里剩下的就是那个唯一的、没有被抵消的数字。 代码回忆清单// 题目LC 136. Single Number class Solution { public int singleNumber(int[] nums) { // 1. 初始化为 0 // 0 ^ x x保证第一个数进去后保持原样 int ans 0; // 2. 遍历所有数字 for (int x : nums) { // 3. 异或累加 (消消乐) // 相同的数字会在过程中互相抵消 ans ^ x; } // 4. 返回幸存者 return ans; } }⚡ 快速复习 CheckList (易错点)[ ]为什么不需要排序因为异或满足交换律。[4, 1, 2, 1, 2]的计算顺序虽然是4^1^2^1^2但数学上等价于4 ^ (1^1) ^ (2^2)。[ ]如果用 HashSet 呢也可以。Set存第一次遇到的删第二次遇到的。最后剩在 Set 里的就是结果。但是 Set 需要 的空间题目进阶要求 空间所以必须用异或。[ ]通用性这个解法只适用于“其他数字都出现偶数次(2次, 4次...)”的情况。如果其他数字出现 3 次需要用位统计法 (LC 137)。️ 数字演练nums [4, 1, 2, 1, 2]初始:ans 0。x 4:ans 0 ^ 4 4。(目前落单的是 4)x 1:ans 4 ^ 1。 (结果是 5二进制 100^001101。暂时看不出意义继续)x 2:ans 4 ^ 1 ^ 2。x 1(关键):ans 4 ^ 1 ^ 2 ^ 1。利用交换律调整视角4 ^ 2 ^ (1 ^ 1)-4 ^ 2 ^ 0。1 被消掉了x 2(关键):ans 4 ^ 2 ^ 0 ^ 2。调整视角4 ^ (2 ^ 2) ^ 0-4 ^ 0 ^ 0。2 被消掉了最终结果:4。
