分析
-
本题的考点:位运算。
-
因为两个相同的数异或值等于0,假设数组中只出现一次的两个数是
a、b
,则将数组中所有数据异或起来的结果s=a^b
,s
一定不等于0,否则说明a==b
,与题意矛盾。 -
因为
s
不等于0,所以我们可以使用lowbit
操作获取x
的最右边一位1,然后根据这一位是否是1将数组中的数据分成两个部分,a、b
分别在这两部分中,每一部分的其余数据都是出现两次,我们可以任选一部分求出其中一个答案,不妨设求出了a
,则b
可以根据b=a^s
直接计算出来。
代码
- C++
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int s = 0;
for (auto x : nums) s ^= x;
// 没有特判数据[1,1,0,-2147483648]在Leetcode无法通过
int t = (s == INT_MIN ? 1 : (s & -s));
int res = 0;
for (auto x : nums) {
if (x & t) res ^= x;
}
return {res, res ^ s};
}
};
- Java
class Solution {
public int[] singleNumber(int[] nums) {
int s = 0;
for (int x : nums) s ^= x;
int t = s & -s; // lowbit
int res = 0;
for (int x : nums) {
if ((x & t) != 0) res ^= x;
}
return new int[]{res, res ^ s};
}
}
时空复杂度分析
-
时间复杂度:$O(n)$,
n
为数组长度。 -
空间复杂度:$O(1)$。