巨详细分析 C++
数组中只出现一次的两个数字
http://www.nowcoder.com/questionTerminal/389fc1c3d3be4479a154f63f495abff8
40、出现2次的数字 题目要求O(n)
(1)根据官宣可知,累加2次用异或得0,全部抵消,相当于只有这两个不同的数字在运算
(2)之前的题里知道双&可以表示进位,这样可以求得这两个数字相加是多少,但好像没什么用。
先来试试比如说1 2 6 1 的异或
+1 -> 1
+2(10) -> 11
+6(110) -> 101
+1 -> 100
当遇到两个一样的时候
虽然010^110=100,在过后看来确实是没有1 的关系,但是在运算的过程中似乎没有体现,也就是你从1->11->101->100过程中不能拿到什么信息。
(3)一个很巧妙的想法:最后的结果是肯定不为0的,因为这两个数字都只出现了一次,那么它们是肯定不相等的,也就是最后的结果汇总肯定至少有一位是1 这个自己想很难想出来 但结论确实合理~
既然已经有一个1了,这两个数字又不同 那么二进制形式中在这一位 肯定有一个数字有1 有一个没有1
按照这个分类标准 两类分别异或出来的就是两个答案,因为其他相同的数肯定会分到同一类。
(4)进行二进制转化:
1/怎么找到那一位,在最后的结果里?
在没什么条件的前提下我们将计就计,用定义来,最后得到的结果因为前面是不停^ 所以是十进制表示的,那么直接%2不为1则/2 ,总能找到某一位是1
比如19%2=1 ,这里得到1了。
不过这个是第几位呢?
19/2=9 ……1
9/2=4 ……1
4/2=2 ……0
2/2=1 ……0
1/2=0 ……1
但是读的时候发现是从上往下读的…… 这样其实第一个得到的1反而在最后一位,所以不用上面那么麻烦。只要得到1,直接乘就是已经判断过的位数(2的几次方 代表这个1后面有几个0)就可以了,不用走完
2/怎么判断某一位有没有1?
我们只放了一个1所以大小会变化.
如果最后结果是10110呢比如这样
判断11010 11010 10100 00010那么先异或10000去了 有1的变小 没1的不变 ok的
代码
class Solution { public: vector<int> FindNumsAppearOnce(vector<int>& array) { int sum=0; for(int i=0;i<array.size();i++) sum=sum^array[i]; int cnt=0; int testp=0; while(sum!=0){ if(sum%2==1)break; cnt++; sum=sum/2; } testp=pow(2,cnt); int ans1=0,ans2=0; for(int i=0;i<array.size();i++){ if(int(array[i]^testp)<array[i]){ ans1=ans1^array[i]; }else{ ans2=ans2^array[i]; } } if(ans1>ans2)return vector<int> {ans2,ans1}; return vector<int> {ans1,ans2}; } };
代码注意:
(1) if(int(array[i]^testp)<array[i]){
判断的时候int可以不用加。括号得加因为有优先极,
array[i]^testp<array[i] 后面先算了
(2)返回一个vector的时候用 { } 用(m,n)是m个值为n的数
vector<int> vec1(4,1); //vec1的内容为1,1,1,1
vector<int> vec1{ 1, 2, 3, 4, 5, 6 }; //vec1内容1,2,3,4,5,6