Leetcode力扣解题记录--第136题（查找单数）
题目链接：136. 只出现一次的数字 - 力扣（LeetCode）
题目描述
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
题目作答
题目的核心要求是 线性时间复杂度 (O(n)) 和 常量额外空间 (O(1))。这两个严格的限制提示我们，不能使用排序（时间不满足）或哈希表（空间不满足）等常规方法。正确的方向是 位运算。
1. 核心工具：异或 (XOR) 运算
解决此问题的关键在于巧妙地利用 异或（XOR） 运算符（在 C++ 中是 ^）的几个关键性质：
-
任何数和 0 做异或运算，结果仍然是原来的数： a ^ 0 = a
-
任何数和其自身做异或运算，结果是 0： a ^ a = 0
-
异或运算满足交换律和结合律： a ^ b ^ c = a ^ (b ^ c) = (a ^ c) ^ b
2. 算法思想
根据这些性质，我们可以得出一个绝妙的推论：
-
如果我们将数组中所有的数字都进行异或运算，那么成对出现的数字会因为 a ^ a = 0 的性质而相互抵消，最终变为 0。
-
所有成对的数字都抵消为 0 之后，只剩下那个唯一的、只出现一次的数字。
-
这个唯一的数字与一堆 0 进行异或运算，根据 a ^ 0 = a 的性质，最终的结果就是这个数字本身。
举例说明: nums = [4, 1, 2, 1, 2]
将所有数字进行异或：4 ^ 1 ^ 2 ^ 1 ^ 2
利用交换律和结合律，我们可以重新排列运算顺序： = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4 ^ 0 = 4
最终的结果 4 就是那个只出现一次的数字。
3. 算法步骤
-
初始化一个变量（例如 result）为 0。
-
遍历 nums 数组中的每一个数字。
-
将 result 与当前遍历到的数字进行异或运算，并将结果赋值回 result。
-
遍历结束后，result 中存储的值就是最终答案。
这种方法只遍历数组一次，时间复杂度为 O(n)；只使用了一个额外的变量，空间复杂度为 O(1)，完美符合题目要求。
class Solution {
public:int singleNumber(vector<int>& nums) {// 初始化结果为0。0与任何数异或都等于那个数本身。int result = 0;// 遍历数组中的所有数字for (int num : nums) {// 将所有数字进行异或运算// 成对的数字会相互抵消变为0// 最终剩下的就是那个唯一的数字result ^= num;}return result;}
}; 