260. 只出现一次的数字 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 中的其他数字都出现两次
题解
思路
暴力解法
class Solution {
public int[] singleNumber(int[] nums) {
int [] result=new int [2];
int n=nums.length;
int k=0;
for(int i=0;i<n;i++){
int showup=0;
for(int j=0;j<n;j++){
if(i==j){
continue;
}else{
if(nums[i]==nums[j]){
showup=1;
break;
}
}
}
if(showup==0){
result[k]=nums[i];
k++;
}
}
return result;
}
}
官方
在理解如何使用位运算解决本题前，读者需要首先掌握「136. 只出现一次的数字」中的位运算做法。
136. 只出现一次的数字
假设数组 nums 中只出现一次的元素分别是 x1 和 x2 。如果把 nums 中的所有元素全部异或起来，得到结果 x，那么一定有：
x = x1 ⊕ x2
其中 ⊕ 表示异或运算。这是因为 nums 中出现两次的元素都会因为异或运算的性质 a⊕b⊕b=a 抵消掉，那么最终的结果就只剩下x1和x2 的异或和。
x 显然不会等于 0，因为如果x=0，那么说明 x1 = x2
这样 x1 和 x2就不是只出现一次的数字了。
因此，我们可以使用位运算 x & -x 取出 x 的二进制表示中最低位那个 1，设其为第 l位，那么 x1 ⊕和x2中的某一个数的二进制表示的第 l位为 0，另一个数的二进制表示的第 l 位为 1。在这种情况下， x1 ⊕ x2的二进制表示的第 l位才能为 1。
这样一来，我们就可以把nums 中的所有元素分成两类，其中一类包含所有二进制表示的第 l 位为 0 的数，另一类包含所有二进制表示的第 l 位为 1 的数。可以发现：
-
对于任意一个在数组nums 中出现两次的元素，该元素的两次出现会被包含在同一类中；
-
对于任意一个在数组 nums 中只出现了一次的元素，即 x1 和 x2，它们会被包含在不同类中。
因此，如果我们将每一类的元素全部异或起来，那么其中一类会得到 x1 ，另一类会得到 x2 。这样我们就找出了这两个只出现一次的元素。
class Solution {
public int[] singleNumber(int[] nums) {
int xorsum = 0;
for (int num : nums) {
xorsum ^= num;
}
// 防止溢出
int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
int type1 = 0, type2 = 0;
for (int num : nums) {
if ((num & lsb) != 0) {
type1 ^= num;
} else {
type2 ^= num;
}
}
return new int[]{type1, type2};
}
}
复杂度分析
-
时间复杂度：O(n)，其中 n 是数组 nums 的长度。
-
空间复杂度：O(1)。
