136. 只出现一次的数字 🟩
题目
LeetCode 简单
给你一个 非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现 线性时间复杂度 的算法来解决此问题，且该算法只使用 常量额外空间。
示例：
输入：nums = [2,2,1]
输出：1
输入：nums = [4,1,2,1,2]
输出：4
输入：nums = [1]
输出：1
常量额外空间
算法在处理数据时，除了输入数组本身，只能用固定数量的额外变量（比如几个整数、指针、布尔值等），不能用与输入规模成比例增长的空间。
- 可以： 用几个变量（如 int a, b, c），无论数组多大，变量数量都不变。
- 不可以： 用数组、哈希表、集合等来存储和辅助查找（因为这些空间会随着输入规模变大而变大）。
题解
位运算
异或（^）
不同时，结果为 1，相同时结果为 0
0^1 = 1，0^0 = 0，1^1 = 0
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)
js
function singleNumber(nums) {
let result = 0
for (let i = 0; i < nums.length; i++) {
result ^= nums[i]
console.log('n', nums[i], 'r', result)
}
return result
}
const nums = [4, 1, 2, 1, 2]
console.log('🌰', singleNumber(nums))n 4 r 4
n 1 r 5
n 2 r 7
n 1 r 6
n 2 r 4
🌰 4