Problem: 136. 只出现一次的数字
题目:给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
文章目录
整体思路
这段代码旨在解决一个非常经典的位运算问题:只出现一次的数字 (Single Number)。问题要求在一个非空整数数组中,除了某个元素只出现一次以外,其余每个元素均出现两次。目标是找出那个只出现了一次的元素。
该算法利用了 异或(XOR) 运算的两个关键性质,以一种极其巧妙和高效的方式解决了这个问题:
异或运算的核心性质:
- 任何数与 0 异或,结果是其本身:
a ^ 0 = a
。 - 任何数与自身异或,结果是 0:
a ^ a = 0
。 - 异或运算满足交换律和结合律:
a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b
。
- 任何数与 0 异或,结果是其本身:
算法逻辑:
- 初始化:算法初始化一个变量
ans
为 0。根据性质1,ans
的初始值不会影响后续的异或结果。 - 累积异或:算法遍历数组中的每一个元素
x
,并将其与ans
进行异或运算,然后将结果存回ans
。即ans = ans ^ x
。 - 最终结果:当遍历完整个数组后,
ans
中存储的就是最终的答案。
- 初始化:算法初始化一个变量
为什么这样可行?
- 假设数组是
[a, b, a, c, c]
。 - 整个异或过程可以看作是
ans = 0 ^ a ^ b ^ a ^ c ^ c
。 - 根据交换律和结合律,这个表达式等价于
ans = (a ^ a) ^ (c ^ c) ^ b ^ 0
。 - 根据性质2,
a ^ a = 0
且c ^ c = 0
。 - 所以表达式变为
ans = 0 ^ 0 ^ b ^ 0
。 - 根据性质1,最终
ans = b
。 - 这个过程可以推广到任意数组:所有出现两次的数,在累积异或的过程中都会两两配对,最终结果变为 0。而那个只出现一次的数,无法找到配对,最终会与一个 0 进行异或,从而保留其自身的值。
- 假设数组是
这个算法构思极为精妙,完美地利用了位运算的特性,提供了一个既不需要额外空间,又具有线性时间复杂度的解决方案。
完整代码
class Solution {
/**
* 在一个非空整数数组中,找出那个只出现一次的元素。
* 数组中其余每个元素均出现两次。
* @param nums 输入的整数数组
* @return 只出现一次的那个元素
*/
public int singleNumber(int[] nums) {
// ans 用于累积所有元素的异或结果。
// 初始化为 0,因为任何数与 0 异或都等于其本身 (a ^ 0 = a)。
int ans = 0;
// 遍历数组中的每一个元素 x
for (int x : nums) {
// 将当前元素 x 与累积结果 ans 进行异或运算。
// 核心原理:
// 1. a ^ a = 0 (任何数与自身异或为 0)
// 2. a ^ b ^ a = b (交换律和结合律)
// 所有出现两次的数字在异或过程中会两两抵消为 0。
// 最终只剩下那个只出现一次的数字与 0 进行异或,结果就是它本身。
ans ^= x;
}
// 返回最终的累积异或结果,即为只出现一次的数字。
return ans;
}
}
时空复杂度
时间复杂度:O(N)
- 循环:算法的核心是一个
for-each
循环,它遍历nums
数组中的每一个元素一次。如果数组的长度为N
,这个循环将执行N
次。 - 循环内部操作:
- 在循环的每一次迭代中,只执行了一次异或运算 (
^=
)。 - 这是一个基本的位运算,时间复杂度是 O(1)。
- 在循环的每一次迭代中,只执行了一次异或运算 (
综合分析:
算法由 N
次 O(1) 的操作组成。因此,总的时间复杂度是 N * O(1)
= O(N)。
空间复杂度:O(1)
- 主要存储开销:算法只使用了
ans
和x
等几个整型变量来存储状态。 - 空间大小:这些变量的数量是固定的,与输入数组
nums
的大小N
无关。
综合分析:
算法没有使用任何与输入规模 N
成比例的额外数据结构(如新数组或哈希表)。因此,其额外辅助空间复杂度为 O(1)。这是一个在时间和空间上都达到最优的解决方案。
参考灵神