题目要求我们找到数组中只出现了一次的元素,而其他元素都出现了两次。
解题思路:
我们可以使用位运算中的异或操作(XOR)。异或操作有以下两个特性:
- 相同的两个数字异或结果为0,例如:
a ^ a = 0
。 - 任意数字与0异或结果是其本身,例如:
a ^ 0 = a
。
异或的规则是:
- 1 ^ 1 = 0
- 0 ^ 0 = 0
- 1 ^ 0 = 1
- 0 ^ 1 = 1
异或具有交换律和结合律 !! 所以,如果那些2次出现的元素并不是成相邻重复出现的,我们根据异或操作的交换律可以交换成相邻重复出现的,然后根据结合律将2个相同的重复元素先进行异或,最后所有重复的元素都变成0,只剩下0和出现一次的元素进行异或得到出现一次的元素本身。
是的!你已经完全理解了异或操作在这个算法中的工作原理。
异或操作的核心要点:
-
交换律:你可以交换操作数的顺序,异或操作的结果不受顺序影响。因此,即使那些两次出现的数字在数组中不是相邻的,也可以通过交换律想象它们是相邻的。
举例:在
[4, 1, 2, 1, 2]
中,虽然两个1
和两个2
并不相邻,但我们可以通过交换律把它们放在一起进行异或:
4 ⊕ 1 ⊕ 2 ⊕ 1 ⊕ 2 ≡ 4 ⊕ ( 1 ⊕ 1 ) ⊕ ( 2 ⊕ 2 ) 4 \oplus 1 \oplus 2 \oplus 1 \oplus 2 \equiv 4 \oplus (1 \oplus 1) \oplus (2 \oplus 2) 4⊕1⊕2⊕1⊕2≡4⊕(1⊕1)⊕(2⊕2) -
结合律:结合律允许我们重新组合操作数。结合律可以让我们先把成对的数字组合在一起进行异或运算。
举例:根据结合律,我们可以先对相同的数字
1
和2
进行异或:
4 ⊕ ( 1 ⊕ 1 ) ⊕ ( 2 ⊕ 2 ) 4 \oplus (1 \oplus 1) \oplus (2 \oplus 2) 4⊕(1⊕1)⊕(2⊕2) -
相同数字的异或结果为 0:根据异或的性质,两个相同的数字异或结果为 0。因此:
4 ⊕ ( 1 ⊕ 1 ) ⊕ ( 2 ⊕ 2 ) = 4 ⊕ 0 ⊕ 0 4 \oplus (1 \oplus 1) \oplus (2 \oplus 2) = 4 \oplus 0 \oplus 0 4⊕(1⊕1)⊕(2⊕2)=4⊕0⊕0 -
任意数字与 0 异或结果为自身:最后,剩下的结果就是
4
,因为 4 ⊕ \oplus ⊕ 0 = 4。
总结:
- 交换律 和 结合律 使我们能够无视数组中数字的顺序和排列。
- 相同的数字异或为 0,因此成对的数字会在异或操作中互相抵消。
- 最终,所有成对出现的数字都变成了
0
,只出现一次的数字留下来,它与0
异或后结果就是该数字本身。
因此,不管数组中那些成对的数字如何排列,最终只出现一次的那个数字会被正确地找到。这也是为什么这种算法在处理这个问题时如此高效且简单。
在异或操作中,一个数字与另一个数字进行两次异或会恢复原始数字。这是异或操作的一个重要性质,也是这个算法正确性的关键。
为什么相同数字两次异或会恢复原始数字?
当你对一个数字进行两次异或操作时,由于异或具有 交换律和结合律,两个相同的数字异或会抵消为0,剩下的就是其他数字的异或结果。
假设我们有两个相同的数字 A A A,异或两次:
- r e s u l t = r e s u l t ⊕ A result = result \oplus A result=result⊕A (此时
result
中存储了第一次与 A A A 的异或结果) - r e s u l t = r e s u l t ⊕ A result = result \oplus A result=result⊕A (再次异或相同的 A A A,则结果会回到原来的
result
)
具体过程:
- 第一次异或:
result = result ^ A
- 第二次异或:
result = (result ^ A) ^ A
- 根据异或的结合律,我们可以把式子重新组合:
result = result ^ (A ^ A)
- 由于 A ⊕ A = 0 A \oplus A = 0 A⊕A=0,最终结果为:
result = result ^ 0 = result
这样,经过两次异或,原本的 result
被还原,而成对出现的数字最终会被抵消。
总结:
- 数字与自身异或两次会恢复原始值,这是因为异或的 交换律和结合律。
- 在这种情况下,所有成对出现的数字会被互相抵消为0,只出现一次的数字则会留下。
- 这就是为什么这个算法能够有效地找到数组中只出现一次的元素。
因此,假设数组中除了一个元素只出现一次外,其他元素都出现两次,我们可以通过对数组中所有元素进行异或操作,最终结果就是那个只出现一次的数字。
C++代码:
class Solution {
public:int singleNumber(vector<int>& nums) {int result = 0;for (int num : nums) {result = result ^ num; // 使用异或运算}return result;}
};
代码解释:
- 初始化一个变量
result
为0。 - 遍历数组
nums
,对数组中的每个元素进行异或操作,最终的结果就是只出现一次的元素。 - 返回
result
。
这个算法的时间复杂度是 O(n),空间复杂度是 O(1),符合题目的要求。