您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode如何找出只出现一次的数字
## 问题描述
在LeetCode题库中，"只出现一次的数字"（Single Number）是一个经典的算法问题。题目描述如下：
> 给定一个非空整数数组，其中某个元素只出现一次，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例：
- 输入: [2,2,1]
- 输出: 1
- 输入: [4,1,2,1,2]
- 输出: 4
## 解决方案
### 方法一：暴力解法（双重循环）
最直观的解决方法是使用双重循环遍历数组，统计每个数字出现的次数：
```python
def singleNumber(nums):
for i in range(len(nums)):
found = False
for j in range(len(nums)):
if i != j and nums[i] == nums[j]:
found = True
break
if not found:
return nums[i]
时间复杂度：O(n²)
空间复杂度：O(1)
利用哈希表（字典）存储数字出现次数：
def singleNumber(nums):
count = {}
for num in nums:
if num in count:
count[num] += 1
else:
count[num] = 1
for num in count:
if count[num] == 1:
return num
时间复杂度：O(n)
空间复杂度：O(n)
利用集合和数学公式 2*(a+b+c) - (a+a+b+b+c) = c：
def singleNumber(nums):
return 2 * sum(set(nums)) - sum(nums)
时间复杂度：O(n)
空间复杂度：O(n)
利用异或（XOR）运算的特性：
- 任何数和0异或都是它本身：a ^ 0 = a
- 任何数和自身异或都是0：a ^ a = 0
- 异或满足交换律和结合律
def singleNumber(nums):
result = 0
for num in nums:
result ^= num
return result
时间复杂度：O(n)
空间复杂度：O(1)
异或运算的二进制表现：
5 ^ 3 = 6
101 (5)
^ 011 (3)
= 110 (6)
在本题中的应用：
[4,1,2,1,2]
4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力解法 | O(n²) | O(1) | 不推荐 |
| 哈希表法 | O(n) | O(n) | 通用解法 |
| 数学运算 | O(n) | O(n) | 需要额外空间 |
| 位运算 | O(n) | O(1) | 最优解，推荐使用 |
这是标准问题，直接用异或解法即可。
此时异或不再适用，需要改用其他方法：
def singleNumber(nums):
ones = twos = 0
for num in nums:
ones = (ones ^ num) & ~twos
twos = (twos ^ num) & ~ones
return ones
需要分组异或：
def singleNumber(nums):
xor = 0
for num in nums:
xor ^= num
mask = 1
while (xor & mask) == 0:
mask <<= 1
a, b = 0, 0
for num in nums:
if num & mask:
a ^= num
else:
b ^= num
return [a, b]
这类算法在以下场景中有实际应用： 1. 数据校验：检测数据传输中的异常值 2. 加密算法：某些加密技术利用异或特性 3. 硬件设计：数字电路中的奇偶校验
通过这个问题，我们学习了： 1. 暴力解法虽然直观但效率低下 2. 哈希表法是通用解法 3. 数学方法展示了巧妙的思路 4. 位运算解法是最优方案
关键点：理解异或运算的特性是解决此类问题的核心。对于面试和算法竞赛，位运算解法通常是考察重点。
建议尝试以下LeetCode类似题目： - 137. Single Number II - 260. Single Number III - 268. Missing Number
掌握这些问题的解法，可以深入理解位运算在算法中的应用。
完整测试用例：
if __name__ == "__main__":
test_cases = [
([2,2,1], 1),
([4,1,2,1,2], 4),
([1], 1)
]
for nums, expected in test_cases:
assert singleNumber(nums) == expected
print("All test cases passed!")
通过系统化的学习和练习，这类问题将不再困难。记住：理解问题本质比死记硬背解法更重要。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。