136. 只出现一次的数字

简单

提示

给你一个非空整数数组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（相互抵消），最后剩下的那个就是落单的数字。”

• 性质 A：N ^ N = 0(自己异或自己，归零)。
• 性质 B：N ^ 0 = N(任何数异或 0，保持不变)。
• 性质 C：满足交换律和结合律 (顺序无所谓，a ^ b ^ c等于a ^ c ^ b)。
• 结论：a ^ b ^ a ^ c ^ b=(a^a) ^ (b^b) ^ c=0 ^ 0 ^ c=c。

2. 算法流程 (Iterative XOR)

1. 初始化 (Init)：

• • ans = 0。因为 0 是异或的单位元（就像加法里的 0，乘法里的 1），它不会改变计算结果。

1. 遍历 (Loop)：

• • 遍历数组中的每一个数x。
  • 执行ans = ans ^ x。
  • 在这个过程中，所有成对出现的数字，无论它们相隔多远，最终都会在异或的数学层面上“相遇”并抵消成 0。

1. 结果 (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]

1. 初始:ans = 0。
2. x = 4:ans = 0 ^ 4 = 4。(目前落单的是 4)
3. x = 1:ans = 4 ^ 1。 (结果是 5，二进制 100^001=101。暂时看不出意义，继续)
4. x = 2:ans = 4 ^ 1 ^ 2。
5. x = 1(关键):

• • ans = 4 ^ 1 ^ 2 ^ 1。
  • 利用交换律调整视角：4 ^ 2 ^ (1 ^ 1)->4 ^ 2 ^ 0。
  • 1 被消掉了！

1. x = 2(关键):

• • ans = 4 ^ 2 ^ 0 ^ 2。
  • 调整视角：4 ^ (2 ^ 2) ^ 0->4 ^ 0 ^ 0。
  • 2 被消掉了！

1. 最终结果:4。