Lt260. 只出现一次的数字 III

260. 只出现一次的数字 III

给定一个整数数组 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 * 104
• -231 <= nums[i] <= 231 - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

思路

sort 后判断当前数和前面后面数都不相同即可。
位运算，遍历先求出异或和，由于其他数都相同，异或和为 0，所以最后求到的就是两个不相同元素的异或和。求出任意一个位数不同的位数作为标记，X & -X 求出二进制下最低的那一位 1.两个不同数，与前面求出的数按位异或，必定处于不同的组当中，其他数异或和为 0，最后求出的两个组的异或和就是两个不同的数。

解答

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function (nums) {
  nums.sort((a, b) => a - b);
  const res = [];
  for (let i = 0; i < nums.length; i++) {
    if (nums[i - 1] !== nums[i] && nums[i + 1] !== nums[i]) res.push(nums[i]);
  }
  return res;
};

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function (nums) {
  let s = 0;
  for (const num of nums) s ^= num;
  const mask = s & (-s + 1);
  let res1 = 0,
    res2 = 0;
  for (const num of nums) {
    if (num & mask) res1 ^= num;
    else res2 ^= num;
  }
  return [res1, res2];
};