125.只出现一次的数字
题目
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
-
输入：nums = [2,2,1]
-
输出：1
思路
核心思路：异或运算（XOR）
什么是异或？
异或是一种位运算，符号是 ^，规则是： - 相同为 0，不同为 1。 - 即：0 ^ 0 = 0，1 ^ 1 = 0，0 ^ 1 = 1。
异或有三个重要性质：
1. 任何数和自己异或结果为 0：a ^ a = 0
2. 任何数和 0 异或结果为自己：a ^ 0 = a
3. 交换律和结合律：a ^ b ^ c = a ^ (b ^ c) = (a ^ c) ^ b
怎么用在这个问题上？
因为数组中除了一个数出现一次，其他数都出现两次，所以如果我们把所有数都异或起来，出现两次的数会互相抵消为 0，最后剩下的就是那个只出现一次的数。
例子：nums = [4,1,2,1,2]
计算过程：
4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2) （利用交换律和结合律）
= 4 ^ 0 ^ 0
= 4 ✅
为什么不用额外空间？
因为只需要一个变量来记录异或结果，不需要哈希表或其他数据结构，空间复杂度 O(1)。
class Solution {
fun singleNumber(nums: IntArray): Int {
var result = 0
for (num in nums) {
result = result xor num // 逐个异或
}
return result
}
}
只出现一次的数字就是：把所有数字异或一遍，出现两次的会互相抵消，剩下的就是答案。
复杂度
- 时间复杂度: O(n)，只需遍历一次数组。
- 空间复杂度: O(1)，只使用了一个变量。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!