只出现一次的数字 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中的其他数字都出现两次
代码结果
运行时间: 23 ms, 内存: 18.1 MB
// 思路：
// 1. 使用位操作与Stream API结合，首先找到两个数的异或结果。
// 2. 计算异或结果中第一个为1的位。
// 3. 使用Stream API和Collectors分组来将数组分为两组。
// 4. 使用reduce进行异或计算得到两个数。
import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;
public class Solution {
public int[] singleNumber(int[] nums) {
// 1. 找到两个数的异或结果
int xor = Arrays.stream(nums).reduce(0, (a, b) -> a ^ b);
// 2. 找到异或结果中为1的最低位
int mask = 1;
while ((xor & mask) == 0) {
mask <<= 1;
}
// 3. 使用mask将数组分为两组，并找到两个数
Map<Boolean, int[]> groups = Arrays.stream(nums).boxed()
.collect(Collectors.partitioningBy(n -> (n & mask) == 0, Collectors.toList()))
.entrySet().stream()
.collect(Collectors.toMap(Map.Entry::getKey, e -> e.getValue().stream().mapToInt(Integer::intValue).toArray()));
int num1 = Arrays.stream(groups.get(true)).reduce(0, (a, b) -> a ^ b);
int num2 = Arrays.stream(groups.get(false)).reduce(0, (a, b) -> a ^ b);
return new int[]{num1, num2};
}
}解释
方法:
该题解使用了位运算的方式来找到只出现一次的两个数字。首先通过对数组中所有元素进行异或操作，得到的结果是两个只出现一次的数字的异或结果（记为a）。在这个结果中，任何为1的位表示这两个数字在该位上有不同的值。然后，选择结果a中任意一个为1的位（通过循环左移mask并与a做与运算直到结果不为0）作为掩码，依据这个掩码将所有数字分成两组，每组内包括一个只出现一次的数字和若干对出现两次的数字。最后，对这两组数字分别进行异或操作，即可得到这两个只出现一次的数字。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在第一次遍历过程中，您是如何确保异或操作最终只得到两个只出现一次数字的异或结果？是否所有出现两次的数字都会被完全抵消？
▷🦆
您在选择位掩码时选择了循环左移并检查异或结果与掩码的与操作直到非零。为什么选择左移而不是右移？这种选择对结果有何影响？
▷🦆
在第二次遍历中，您是如何保证，按照掩码分组后，每组内的元素确实只包括一个只出现一次的数字和若干对出现两次的数字？是否有可能出现掩码无法正确分组的情况？
▷