0260. 只出现一次的数字 III【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 异或运算

1. 📝 题目描述

• leetcode

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

---

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

---

提示：

• 2 <= nums.length <= 3 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

2. 🎯 s.1 - 异或运算

js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function (nums) {
  let xor = 0

  // 全部异或，得到两个只出现一次的数的异或值
  for (const num of nums) {
    xor ^= num
  }

  // 找到最低位为 1 的掩码
  const rightmostBit = xor & ~(xor - 1)

  let num1 = 0
  let num2 = 0

  // 根据最低位 1 分组
  for (const num of nums) {
    if (num & rightmostBit) {
      num1 ^= num
    } else {
      num2 ^= num
    }
  }

  return [num1, num2]
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$
• 相同解法的例题：645. 错误的集合