企业官网建设流程全解析

题目：

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

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

题解：

我觉着这是很有意思的一道题

该问题看似简单，但在时间和空间复杂度限制下，非常考察对位运算的理解。

一、最直观的思路（为什么不选）

1，使用哈希表统计次数

最容易想到的方式是：

• 使用哈希表记录每个数字出现的次数

• 再遍历哈希表，找出次数为 1 的元素

问题：

• 需要额外的存储空间

• 空间复杂度为O(n)

而本题的隐含要求是：
使用常量额外空间

2， 排序后相邻比较

另一种思路是：

• 对数组排序

• 成对比较相邻元素

问题：

• 排序时间复杂度至少为O(n log n)

• 不满足最优解要求

二、最优解的核心思想：异或运算

1，什么是异或（XOR）

异或运算有几个非常重要的性质：

1. 相同的数异或为 0

   a ^ a = 0

2. 任何数与 0 异或仍是它本身

   a ^ 0 = a

3. 异或满足交换律和结合律

   a ^ b ^ a = b

2，这些性质意味着什么？

在数组中：

• 每个出现两次的数字：

  x ^ x = 0

• 所有成对的数字最终都会“抵消”为 0

• 剩下的唯一一个数：

  0 ^ single = single

只出现一次的数字一定会被保留下来

三、算法思路（核心逻辑）

1. 初始化一个变量res = 0

2. 遍历数组中每一个元素

3. 将当前元素与res进行异或运算

4. 遍历结束后，res就是只出现一次的数字

整个过程：

• 不需要额外的数据结构

• 只做一次遍历

• 完全利用位运算完成

四、总结

• 本题的关键不在于遍历，而在于如何“消掉”重复元素

• 异或运算天然适合处理：

  • 成对出现

  • 只剩一个不同值

• 这是位运算在算法题中的经典应用

一句话总结：

利用异或“相同为零、不同保留”的特性，让所有成对数字互相抵消，最终剩下的就是答案。

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