题目描述

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

你需要设计并实现一个线性时间复杂度的算法来解决此问题，并且该算法只能使用常量额外空间。

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

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

异或运算

异或运算（XOR，也称为按位异或运算）是一种二进制位运算，它在计算机科学中非常重要。异或运算的操作规则非常简单：对于两个二进制位，如果它们相同则结果为0，如果它们不同则结果为1。

符号表示

异或运算通常用符号 “⊕” 或者 “^” 表示。在许多编程语言中，用符号 “^” 来表示异或运算。例如，在C++中，你可以使用 ^ 运算符来执行异或运算。

运算性质

交换律：对于任何整数 a 和 b，a ⊕ b 等于 b ⊕ a。也就是说，异或运算是可交换的。
结合律：对于任何整数 a、b 和 c，(a ⊕ b) ⊕ c 等于 a ⊕ (b ⊕ c)。也就是说，异或运算是可结合的。
自反性：对于任何整数 a，a ⊕ a 等于 0。也就是说，一个数与自己做异或运算的结果是0。
零元素：对于任何整数 a，a ⊕ 0 等于 a。也就是说，一个数与0做异或运算的结果是它本身。

计算过程

假设我们要计算 5 ⊕ 3：

首先，将这两个数表示为二进制形式：
- 5 的二进制表示是：101
- 3 的二进制表示是：011
然后，从右向左按位进行异或运算。在每个位置上，如果两个对应的位相同（都是1或都是0），结果就是0；如果两个对应的位不同，结果就是1。
- 第一个位：1 ⊕ 1 = 0
- 第二个位：0 ⊕ 1 = 1
- 第三个位：1 ⊕ 0 = 1
将结果组合起来，得到最终的二进制表示：110。
最后，将二进制结果转换回十进制，得到最终结果：6。

所以，5 ⊕ 3 的计算结果是 6。

应用

交换变量的值：可以使用异或运算来交换两个变量的值而不需要额外的临时变量。

int a = 5, b = 7;
a = a ^ b;
b = a ^ b;
a = a ^ b;
// 现在 a = 7，b = 5

检查奇偶性：通过将一个整数与1进行异或运算，可以快速确定该整数是奇数还是偶数。

int num = 6;
if (num & 1) {
    // num 是奇数
} else {
    // num 是偶数
}

数据加密：异或运算在数据加密和解密中有广泛应用。

假设我们有一个简单的加密算法，其中我们将明文（原始文本）与一个密钥进行异或运算以生成密文（加密文本）。解密时，只需再次对密文与相同的密钥进行异或运算，就可以还原明文。

例如，我们使用密钥 1010 对明文 1100 进行加密：

明文 1100
密钥 1010
密文 0110

解密时，我们再次对密文 0110 与相同的密钥 1010 进行异或运算：

密文 0110
密钥 1010
明文 1100

答案解析

当一个整数数组中只有一个元素出现一次，而其他所有元素都出现两次时，可以使用异或运算来解决这个问题。异或运算有一个有用的性质，即任何数与自己做异或运算的结果都是0，而任何数与0做异或运算的结果都是它本身。因此，如果我们将数组中的所有元素进行异或运算，成对出现的元素会相互抵消，最终剩下的就是只出现一次的元素。

初始化一个变量 result 为0，用来存储最终的结果。
遍历整个数组 nums，对每个元素进行异或运算，将结果存储在 result 中。由于异或运算满足交换律和结合律，相同的元素都会相互抵消，最终 result 中将只包含出现一次的元素。
返回 result，它就是只出现一次的元素。

#include <iostream>
#include <vector>

int singleNumber(std::vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

int main() {
    std::vector<int> nums = {2, 2, 1, 4, 4};
    int result = singleNumber(nums);
    std::cout << "The single number is: " << result << std::endl;
    return 0;
}