【LeetCode 热题 100】136. 只出现一次的数字——异或

Problem: 136. 只出现一次的数字
题目：给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

整体思路

这段代码旨在解决一个非常经典的位运算问题：只出现一次的数字 (Single Number)。问题要求在一个非空整数数组中，除了某个元素只出现一次以外，其余每个元素均出现两次。目标是找出那个只出现了一次的元素。

该算法利用了 异或（XOR） 运算的两个关键性质，以一种极其巧妙和高效的方式解决了这个问题：

1. 异或运算的核心性质：

   • 任何数与 0 异或，结果是其本身：a ^ 0 = a。
   • 任何数与自身异或，结果是 0：a ^ a = 0。
   • 异或运算满足交换律和结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b。

2. 算法逻辑：

   • 初始化：算法初始化一个变量 ans 为 0。根据性质1，ans 的初始值不会影响后续的异或结果。
   • 累积异或：算法遍历数组中的每一个元素 x，并将其与 ans 进行异或运算，然后将结果存回 ans。即 ans = ans ^ x。
   • 最终结果：当遍历完整个数组后，ans 中存储的就是最终的答案。

3. 为什么这样可行？

   • 假设数组是 [a, b, a, c, c]。
   • 整个异或过程可以看作是 ans = 0 ^ a ^ b ^ a ^ c ^ c。
   • 根据交换律和结合律，这个表达式等价于 ans = (a ^ a) ^ (c ^ c) ^ b ^ 0。
   • 根据性质2，a ^ a = 0 且 c ^ c = 0。
   • 所以表达式变为 ans = 0 ^ 0 ^ b ^ 0。
   • 根据性质1，最终 ans = b。
   • 这个过程可以推广到任意数组：所有出现两次的数，在累积异或的过程中都会两两配对，最终结果变为 0。而那个只出现一次的数，无法找到配对，最终会与一个 0 进行异或，从而保留其自身的值。

这个算法构思极为精妙，完美地利用了位运算的特性，提供了一个既不需要额外空间，又具有线性时间复杂度的解决方案。

完整代码

class Solution {
    /**
     * 在一个非空整数数组中，找出那个只出现一次的元素。
     * 数组中其余每个元素均出现两次。
     * @param nums 输入的整数数组
     * @return 只出现一次的那个元素
     */
    public int singleNumber(int[] nums) {
        // ans 用于累积所有元素的异或结果。
        // 初始化为 0，因为任何数与 0 异或都等于其本身 (a ^ 0 = a)。
        int ans = 0;
        
        // 遍历数组中的每一个元素 x
        for (int x : nums) {
            // 将当前元素 x 与累积结果 ans 进行异或运算。
            // 核心原理：
            // 1. a ^ a = 0 (任何数与自身异或为 0)
            // 2. a ^ b ^ a = b (交换律和结合律)
            // 所有出现两次的数字在异或过程中会两两抵消为 0。
            // 最终只剩下那个只出现一次的数字与 0 进行异或，结果就是它本身。
            ans ^= x;
        }
        
        // 返回最终的累积异或结果，即为只出现一次的数字。
        return ans;
    }
}

时空复杂度

时间复杂度：O(N)

1. 循环：算法的核心是一个 for-each 循环，它遍历 nums 数组中的每一个元素一次。如果数组的长度为 N，这个循环将执行 N 次。
2. 循环内部操作：
   • 在循环的每一次迭代中，只执行了一次异或运算 (^=)。
   • 这是一个基本的位运算，时间复杂度是 O(1)。

综合分析：
算法由 N 次 O(1) 的操作组成。因此，总的时间复杂度是 N * O(1) = O(N)。

空间复杂度：O(1)

1. 主要存储开销：算法只使用了 ans 和 x 等几个整型变量来存储状态。
2. 空间大小：这些变量的数量是固定的，与输入数组 nums 的大小 N 无关。

综合分析：
算法没有使用任何与输入规模 N 成比例的额外数据结构（如新数组或哈希表）。因此，其额外辅助空间复杂度为 O(1)。这是一个在时间和空间上都达到最优的解决方案。

参考灵神