题目描述

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

你必须在线性时间复杂度（O(n)）和常数额外空间（O(1)）的限制下完成这个问题。

示例 1：

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

示例 2：

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

示例 3：

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

解法

题目要求 O(n) 时间复杂度和 O(1) 空间复杂度，我们可以使用 异或（XOR）运算 来解决。

异或运算性质

  1. a ⊕ a = 0（任何数和自己异或结果为 0）
  2. a ⊕ 0 = a（任何数和 0 异或不变）
  3. a ⊕ b ⊕ c = a ⊕ c ⊕ b（异或运算满足交换律和结合律）

由于数组中除了一个数出现 1 次，其余的数都出现 2 次，那么所有数字进行异或运算后：

  • 成对出现的数会互相抵消变成 0
  • 最终只剩下那个只出现一次的数

C++ 代码

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

时间复杂度分析

  • 遍历一次数组，时间复杂度为 O(n)
  • 仅用一个整数存储异或结果，空间复杂度为 O(1)

C++运算符知识补充

在 C++ 中，运算符（Operators）是对变量或值执行操作的符号。常见的运算符包括 算术运算符、位运算符、逻辑运算符、关系运算符、赋值运算符 等。

类型 主要运算符
算术 + - * / % ++ --
赋值 = += -= *= /= %=
关系 == != > < >= <=
逻辑 && \ \ !
位运算 & \ ^ ~ << >>
杂项运算 ? : sizeof

1. 逻辑运算符（Logical Operators）

逻辑运算符通常用于布尔判断：

运算符 作用
&& 逻辑与（AND）：两者都为 true 才返回 true
`
! 逻辑非（NOT）：取反 
bool a = true, b = false;
cout << (a && b) << endl;  // 0 (false)
cout << (a || b) << endl;  // 1 (true)
cout << (!a) << endl;      // 0 (false)

2. 位运算符（Bitwise Operators）

位运算符用于直接操作二进制位：

运算符 作用
& 按位与（AND）：两个位都为 1，结果才为 1
\ 按位或（Bitwise OR）：只要有一个位是 1，结果就是 1
^ 按位异或（XOR）：相同为 0，不同为 1
~ 按位取反（NOT）：所有位取反
<< 左移（Left Shift）：向左移动 n 位，低位补 0
>> 右移（Right Shift）：向右移动 n 位，丢弃低位 
int a = 5, b = 3;  // 5 = 0101, 3 = 0011
cout << (a & b) << endl;  // 0001 = 1
cout << (a | b) << endl;  // 0111 = 7
cout << (a ^ b) << endl;  // 0110 = 6
cout << (~a) << endl;     // 取反 (按 32 位计算，~5 = -6)
cout << (a << 1) << endl; // 1010 = 10  (左移一位)
cout << (a >> 1) << endl; // 0010 = 2   (右移一位)

3. 条件（三目）运算符（Ternary Operator）

格式：
(条件) ? (如果为 true 返回) : (如果为 false 返回);

int a = 10, b = 5;
int minVal = (a < b) ? a : b;
cout << minVal << endl;  // 5