只出现一次的数字

题面

给你一个 非空 整数数组 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

• 除了某个元素只出现一次以外，其余每个元素均出现两次。

分析

• 最朴素的想法是使用哈希表，来实现线性时间复杂度，但是会需要额外的空间

• 可以利用异或运算的三个关键特性： 1.自反性：任何数和自身异或结果为 0（a ^ a = 0）； 2.归零性：任何数和 0 异或结果为自身（a ^ 0 = a）； 3.交换律 / 结合律：a ^ b ^ c = a ^ c ^ b = (a ^ b) ^ c。

• 基于这些特性，将数组中所有元素依次异或：

  • 出现两次的元素会两两异或得到 0；
  • 最终剩下的结果就是只出现一次的那个元素（0 异或该元素 = 该元素）

• 代码实现

  class Solution {
  public:
      int singleNumber(vector<int>& nums) {
          int result = 0; // 初始化为0，因为0异或任何数不改变其值
          for (int num : nums) {
              result ^= num; // 依次异或数组中的每个元素
          }
          return result;
      }
  };