260. 只出现一次的数字 III

🟠   🔖  位运算 数组  🔗 力扣 LeetCode

题目

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5]

Output: [3,5]

Explanation: [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]

Output: [-1,0]

Example 3:

Input: nums = [0,1]

Output: [1,0]

Constraints:

• 2 <= nums.length <= 3 * 10^4
• -231 <= nums[i] <= 231 - 1
• Each integer in nums will appear twice, only two integers will appear once.

题目大意

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

解题思路

1. 异或的性质

   • a ^ a = 0，即相同数字异或为 0。
   • a ^ 0 = a，即数字与 0 异或等于它本身。
   • 异或操作满足交换律和结合律。

2. 异或结果的意义

   • 如果将所有数字进行异或，得到的结果是这两个不同数字的异或值，设为 xor。
   • 这个 xor 中每一位为 1 表示在两个不同数字的这一位上值不同。

3. 分组

   • 根据 xor 中某一位为 1 的位置（称为分组标志位），可以将数组中的数字分为两组：
     • 一组在该位为 1。
     • 另一组在该位为 0。
   • 这样，两个只出现一次的数字会被分到不同组，而其他出现两次的数字由于相同，仍然会在各自组内抵消为 0。
   • 对每组数字分别异或，得到结果。

复杂度分析

• 时间复杂度：O(n)，遍历数组两次，一次遍历数组计算异或，一次遍历数组分组并计算两个数字。
• 空间复杂度：O(1)，使用了常数额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function (nums) {
	// 异或所有数字，得到两个不同数字的异或结果
	const xor = nums.reduce((a, b) => a ^ b, 0);

	// 找到 xor 中第一个为 1 的位
	let pos = 0;
	while (((xor >> pos) & 1) !== 1) {
		pos += 1;
	}

	// 根据该位将数字分为两组
	let res = [0, 0];
	for (let num of nums) {
		if (((num >> pos) & 1) == 1) {
			// 该位为 1 的分到第一组
			res[0] ^= num;
		} else {
			// 该位为 0 的分到第二组
			res[1] ^= num;
		}
	}

	// 返回结果
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
136	只出现一次的数字	[✓]	位运算 数组	🟢	🀄️ 🔗
137	只出现一次的数字 II	[✓]	位运算 数组	🟠	🀄️ 🔗
2433	找出前缀异或的原始数组		位运算 数组	🟠	🀄️ 🔗
3158	求出出现两次数字的 XOR 值		位运算 数组 哈希表	🟢	🀄️ 🔗