当前位置：首页 > ds >正文

136. 只出现一次的数字

ds 2025/7/4 2:29:02

一、问题描述

二、解题思路

三、代码

四、复杂度分析

一、问题描述

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

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

二、解题思路

异或 XOR 的几个性质：

a ^ a = 0（任何数和自己异或为0）
a ^ 0 = a（任何数和0异或还是它本身）
异或满足 交换律 和 结合律：a ^ b ^ c = a ^ (b ^ c)

所以如果一个数组中：

所有元素都出现两次，只有一个元素出现一次
那么我们把数组里所有数字都异或一遍，成对的数会变成 0，最终结果就是那个 只出现一次的数

示例：

cpp

复制编辑

nums = [2, 3, 2, 3, 5]

这里：

2 出现了两次
3 出现了两次
只有 5 出现了一次，结果应该返回 5

🚀 为什么用异或？

🔢 异或的核心特点：

操作	结果	含义
`a ^ a`	`0`	自己跟自己异或等于 0
`a ^ 0`	`a`	任何数与 0 异或还是它自己
异或满足交换律和结合律	`a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b`	顺序不重要

✅ 用异或解这道题的逻辑：

假设你从左到右，遍历 nums，把所有数都异或到一个变量 result 中。

由于所有数都出现两次，它们“配对异或”之后变成了 0，只有那个“只出现一次”的数还剩下来！

🧮 举个完整例子：

nums = [4, 1, 2, 1, 2]

我们用异或来操作：

步骤	当前数字	异或结果 (`result`)
初始	-	`0`（初始值）
1	`4`	`0 ^ 4 = 4`
2	`1`	`4 ^ 1 = 5`
3	`2`	`5 ^ 2 = 7`
4	`1`	`7 ^ 1 = 6`
5	`2`	`6 ^ 2 = 4`

最后结果是 4，就是我们想找的答案！

三、代码

class Solution {
public:int singleNumber(vector<int>& nums) {int result = 0; // 初始结果设为 0// 遍历数组中的所有元素for (int num : nums) {result ^= num; // 把每个数和 result 做异或}return result; // 最后剩下的就是只出现一次的数}
};