巨详细分析 C++

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