本文最后更新于 354 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
给你一个整数数组 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
中的其他数字都出现两次
解法一:位运算
算法思路:
首先了解异或运算的性质:
- 任何数和自己做异或运算,结果是 0,即
x ⊕ x = 0
。 - 任何数和 0 做异或运算,结果任然是原来的数,即
x ⊕ 0 = x
。
假设数组 nums 中只出现一次的元素分别是 x1 和 x2,如果把 nums 中的元素全部异或起来,得到结果x,那么有:
$$
x=x1⊕x2
$$
由于 x1 和 x2 不相同,所以 x 显然不会为 0 ,那么我们使用位运算 x & -x
取出 x 的二进制位中最低位的 1,设为第 l
位,显然 x1 和x2在 l
位上有一个为 0,另一个为 1。
那么,我们可以把 nums 中的所有元素分为两类,其中一类包含所有二进制第 l
位为 0 的数,另一类包含所有二进制第 l
位为 1 的数。可以发现:
- 对于任意一个在数组 nums 中出现过两次的元素,该元素的两次出现会被包含在同一类中。
- 对于任意一个在数组 nums 中只出现一次的元素,即 x1 和 x2,他们会被包含在不同类中。
因此,我们将每一类的所有元素都异或起来,就可以得到 x1 和 x2。
代码实现:
class Solution {
public int[] singleNumber(int[] nums) {
int xs = 0;
for(int num : nums){
xs ^= num;
}
int lb = xs & -xs;
int a = 0;
for(int num : nums){
if((num & lb) != 0){
a ^= num;
}
}
int b = xs ^ a;
return new int[] {a, b};
}
}
复杂度分析:
时间复杂度: O(n),其中n为数组nums的长度。
空间复杂度: O(1)。