目录
题目
解析
完整代码:
题目
我们首先看一下题目:
给定一个整数数组 nums
,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
![](https://img-blog.csdnimg.cn/6410407acb604b4cb16d8451131f910c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6KGo5ZOl5oqx6KGo5byf,size_20,color_FFFFFF,t_70,g_se,x_16)
接口:
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
}
};
解析
我们看到这种题目首先想到的是异或:两个相同的数字异或后为0,这里我们拿6做演示:
![](https://img-blog.csdnimg.cn/97cba783fcc64656a030be8672cefac2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6KGo5ZOl5oqx6KGo5byf,size_20,color_FFFFFF,t_70,g_se,x_16)
//1.首先亦或
long sum1=0;
for(auto e:nums){
sum1^=e;
}
但是问题来了:我们全部异或之后得到的数字为不为0的数字是两个出现一次的数字的异或,我们怎么来将这两个数字分离出来呢?这个分离很难有头绪.我们可以用这个异或的结果来分析:
假设序列为:1 2 2 1 3 6
异或之后的结果为:0101
我们发现这个数字是一个不为0的数字,这个比特位为1的地方是两个单身数字不同才可以异或为1.
我们可以根据这个比特位为1的不同来对数组进行分组,将两个出现一次的数字分到两个组里面分别异或,最后得到的就是两个单独的数字.我们要得到的数字是0001,这个数字与原数组再进行与操作,结果为0的一组,为1的另一组:
![](https://img-blog.csdnimg.cn/742ff26724fd4ce2a3931d42a74881a1.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6KGo5ZOl5oqx6KGo5byf,size_20,color_FFFFFF,t_70,g_se,x_16)
那么我们怎么得到这个比特位的数字呢?
重点来了:我们对这个第一次异或完的数字取他的负数再与原来的数字与(说的有点复杂其实很简单):
![](https://img-blog.csdnimg.cn/9ce794e4e80a4762a77c8d700b8da13d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6KGo5ZOl5oqx6KGo5byf,size_20,color_FFFFFF,t_70,g_se,x_16)
//2.sum1肯定是不为0的数字,两个不同的数字进行亦或,我们只需要分组
int sum2=sum1&(-sum1);//找到sum1二进制第一个1的位置
最后我们只需要以这个为条件来进行分组异或即可:
for(auto e:nums){
if(e&sum2){//1分一组
ret[0]^=e;
}else{//0为一组
ret[1]^=e;
}
}
完整代码:
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> ret(2);
//1.首先亦或
long sum1=0;
for(auto e:nums){
sum1^=e;
}
//2.sum1肯定是不为0的数字,两个不同的数字进行亦或,我们只需要分组
int sum2=sum1&(-sum1);//找到sum1二进制第一个1的位置
for(auto e:nums){
if(e&sum2){//1分一组
ret[0]^=e;
}else{//0为一组
ret[1]^=e;
}
}
return ret;
}
};
![](https://img-blog.csdnimg.cn/644aef1fa19f4621b17cc4fc8f205466.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6KGo5ZOl5oqx6KGo5byf,size_20,color_FFFFFF,t_70,g_se,x_16)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)