利用异或操作高效解决数组中唯一出现一次的元素问题

在编程中，我们经常遇到一些需要高效解决的问题。今天就来讨论一个经典的算法问题：在一个非空整数数组中，除了某个元素只出现一次以外，其余每个元素均出现两次。需要找到这个唯一出现一次的元素。要求算法的时间复杂度为线性，并且只使用常量额外空间。

问题描述

给定一个非空整数数组 nums，其中除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

提示：

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

异或操作简介

在解决这个问题之前，需要先了解一种重要的位运算操作——异或（XOR）。异或操作符通常用 ^ 表示。它对两个二进制数的每一位进行比较，如果两个对应位不同，则结果为1；如果相同，则结果为0。

异或操作的性质

1. 自反性：a ^ a = 0
   任何数与自身异或结果为0。
   例如：5 ^ 5 = 0
2. 恒等性：a ^ 0 = a
   任何数与0异或结果为其本身。
   例如：5 ^ 0 = 5
3. 交换性：a ^ b = b ^ a
   异或操作具有交换性。
   例如：5 ^ 3 = 3 ^ 5
4. 结合性：(a ^ b) ^ c = a ^ (b ^ c)
   异或操作具有结合性。
   例如：(5 ^ 3) ^ 2 = 5 ^ (3 ^ 2)

利用异或解决问题

可以利用异或操作的这些性质来高效解决这个问题。具体来说，可以通过逐步应用异或操作来消除成对的元素，最终剩下的就是那个只出现一次的元素。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        single_num = 0
        for num in nums:
            single_num ^= num
        return single_num

逐步计算过程

通过一个具体的例子来理解这个算法。考虑输入数组 nums = [4,1,2,1,2]：

1. 初始 single_num = 0，二进制表示为 000
2. single_num ^= 4 -> single_num = 4，二进制表示为 100（因为 000 ^ 100 = 100）
3. single_num ^= 1 -> single_num = 5，二进制表示为 101（因为 100 ^ 001 = 101）
4. single_num ^= 2 -> single_num = 7，二进制表示为 111（因为 101 ^ 010 = 111）
5. single_num ^= 1 -> single_num = 6，二进制表示为 110（因为 111 ^ 001 = 110）
6. single_num ^= 2 -> single_num = 4，二进制表示为 100（因为 110 ^ 010 = 100）

最终 single_num 的值是4，即只出现一次的元素。

总结

通过利用异或操作的性质，可以在 O(n) 时间复杂度和 O(1) 空间复杂度下高效地找到数组中唯一出现一次的元素。这种方法不仅简洁高效，而且非常适合处理成对出现的元素问题。