136. 只出现一次的数字

给你一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例：

输入：nums = [4,1,2,1,2]
输出：4

解题思路

• 位运算中，对任何数，都有 x ^ x === 0; 和 x ^ 0 === x;
  • 2 个相同数字进行异或运算，结果为 0。
  • 任何数字和 0 进行异或运算，结果为数字本身。
• 交换律 (a ^ b) ^ c === a ^ (b ^ c);，异或计算顺序不影响最终结果。

所以，遍历数组进行异或计算，重复的数字计算后为 0，最后剩下唯一一个不重复数字。

0 ^ 4; // 4
2 ^ 2; // 0
1 ^ 1; // 0

参考答案

function singleNumber(nums: number[]): number {
  let ans = 0;
  for (let i = 0; i < nums.length; ++i) {
    ans ^= nums[i];
  }
  return ans;
};