异或消除重复

为什么异或能找到只出现一次的元素？

• 问题: 除一个元素只出现一次外, 其余元素都出现两次, 找出该元素;
• 依据: a ^ a = 0, a ^ 0 = a, 且异或满足交换律与结合律;
• 把全部元素异或起来, 成对的元素互相抵消, 剩下的就是只出现一次的元素;

异或找单独元素如何实现？

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

异或消除重复的复杂度是多少？

• 时间复杂度: O(n), 一次遍历;
• 空间复杂度: O(1), 只用一个累加变量;