LeetCode 第136题：只出现一次的数字

题目描述

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

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

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

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

解题思路

方法一：位运算（异或）

这道题要求我们找出数组中只出现一次的元素，其他元素都出现两次。我们可以利用异或运算的特性来解决这个问题。

关键点：

异或运算的特性：a ^ a = 0（相同的数异或结果为0）
异或运算的特性：a ^ 0 = a（任何数与0异或结果为其本身）
异或运算满足交换律和结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

具体步骤：

初始化结果变量result = 0
遍历数组中的每个元素：
- 将result与当前元素进行异或运算：result ^= nums[i]
最终result的值就是只出现一次的元素

时间复杂度：O(n)，其中n是数组的长度。只需要遍历一次数组。空间复杂度：O(1)，只需要常数级别的额外空间。

方法二：哈希表

另一种解决方案是使用哈希表来记录每个元素出现的次数。

关键点：

使用哈希表记录每个元素出现的次数
遍历哈希表，找出出现次数为1的元素

具体步骤：

创建一个哈希表，用于记录每个元素出现的次数
遍历数组中的每个元素：
- 如果元素不在哈希表中，将其加入哈希表，次数设为1
- 如果元素已在哈希表中，将其次数加1
遍历哈希表，找出出现次数为1的元素

时间复杂度：O(n)，其中n是数组的长度。需要遍历一次数组和一次哈希表。空间复杂度：O(n)，需要使用哈希表存储数组中的元素。

图解思路

异或运算过程分析表

以示例2为例：nums = [4,1,2,1,2]

索引	nums[i]	result	操作	说明
初始状态	-	0	-	初始化result为0
0	4	4	0 ^ 4 = 4	4与0异或得到4
1	1	5	4 ^ 1 = 5	4与1异或得到5
2	2	7	5 ^ 2 = 7	5与2异或得到7
3	1	6	7 ^ 1 = 6	7与1异或得到6（1出现两次，相当于没有1）
4	2	4	6 ^ 2 = 4	6与2异或得到4（2出现两次，相当于没有2）

最终结果：4

哈希表过程分析表

以示例2为例：nums = [4,1,2,1,2]

索引	nums[i]	哈希表	操作	说明
初始状态	-	{}	-	初始化空哈希表
0	4	{4: 1}	添加4，次数为1	4首次出现
1	1	{4: 1, 1: 1}	添加1，次数为1	1首次出现
2	2	{4: 1, 1: 1, 2: 1}	添加2，次数为1	2首次出现
3	1	{4: 1, 1: 2, 2: 1}	1的次数加1，变为2	1第二次出现
4	2	{4: 1, 1: 2, 2: 2}	2的次数加1，变为2	2第二次出现

遍历哈希表，找出次数为1的元素：4

代码实现

C# 实现

public class Solution {
    public int SingleNumber(int[] nums) {
        int result = 0;
        
        foreach (int num in nums) {
            result ^= num;
        }
        
        return result;
    }
}

Python 实现

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        
        for num in nums:
            result ^= num
        
        return result

C++ 实现

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

执行结果

C# 实现

执行用时：96 ms
内存消耗：42.5 MB

Python 实现

执行用时：36 ms
内存消耗：17.1 MB

C++ 实现

执行用时：12 ms
内存消耗：16.8 MB

性能对比

语言	执行用时	内存消耗	特点
C#	96 ms	42.5 MB	执行速度适中，内存消耗较高
Python	36 ms	17.1 MB	执行速度适中，内存消耗适中
C++	12 ms	16.8 MB	执行速度最快，内存消耗最低

代码亮点

🎯 利用异或运算的特性，一行代码解决问题
💡 时间复杂度为O(n)，空间复杂度为O(1)，满足题目要求
🔍 不需要额外的数据结构，代码简洁高效
🎨 适用于所有编程语言，通用性强

常见错误分析

🚫 使用排序算法，导致时间复杂度为O(n log n)，不满足题目要求
🚫 使用哈希表，导致空间复杂度为O(n)，不满足题目要求
🚫 没有考虑数组中可能有负数的情况
🚫 使用累加和减法，可能导致整数溢出

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
位运算（异或）	O(n)	O(1)	时间和空间效率都很高	需要理解异或运算的特性
哈希表	O(n)	O(n)	思路直观，易于理解	空间复杂度较高，不满足题目要求
排序	O(n log n)	O(1)	思路简单	时间复杂度较高，不满足题目要求

题目描述

难度

题目链接

示例

示例 1：

示例 2：

示例 3：

提示

解题思路

方法一：位运算（异或）

方法二：哈希表

图解思路

异或运算过程分析表

哈希表过程分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目