题目描述
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。2 <= nums.length <= 1000
样例
输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]
位运算
我的第一想法是map来做,但是题目限制很大。
我看的K神的题解,这里想把我理解到的意思表达出来。
现在开始:
异或:
a ^ b ^ c ^ a = b ^ c;
a ^ b = b ^ a
我们知道 两个 不同的数字 ,在二进制下,至少有一位是不同的
比如 4:0100 ; 8:1000
那么 4 ^ 8 = 1100
我们就需要一个变量 m去找到哪一位不同
4和8的话,就是在第三位(从左往右)。那么我们就记录下来m当前值。
这里就需要位与(&)运算 。遍历异或的值。当相与为1的时候,就是 m记录下来的值。
我们知道了从哪位开始不同,那么接下来就是把 这个值分成两组。遍历数组的值,看相与m之间的关系。
一组就直接异或,直到所以数组遍历完成,接下来看代码。
参考文献
C++ 第一版本代码
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int x = 0 ,y = 0, m = 1,n = 0;
int len = nums.size();//长度
for(int i = 0;i < len;i ++) n ^= nums[i];// 找到只出现一次的两个数字相与
while((n&m) ==0){// 找出哪一位是不同的 ,记录下m的值
m <<= 1;
}
for(int i = 0;i < len;i ++) {// 这里就是分组,得出两个答案
if(m & nums[i]) x ^= nums[i];
else y ^= nums[i];
}
return {x,y};
}
};
C++ 简洁代码
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int x = 0, y = 0, n = 0, m = 1;
for(int num : nums) //这是遍历容器的方式
n ^= num;
while((n & m) == 0) // 2. 循环左移,计算 m
m <<= 1;
for(int num : nums) { // 3. 遍历 nums 分组
if(num & m) x ^= num; // 4. 当 num & m != 0
else y ^= num; // 4. 当 num & m == 0
}
return vector<int> {x, y}; // 5. 返回出现一次的数字
}
};