leetcode136，137，260：只出现一次的数字 | || |||

leetcode 136.只出现一次的数字 |

用位运算就可以，相当的简单。
异或：不相同异或为1，相同异或为0。
结论：相同的数字异或为0。任何数和0异或都是自己本身。
验证：

对于这道题，可以用0和数组里的每个数都异或，最终结果就只出现一次的数字。对吧？因为数组里相同的数字异或结果为0，0和只出现一次的数字异或为其本身。

题解：

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int n=0;
        for(int num:nums)
        {
            n=n^num;
        }
        return n;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

不会用范围for的，可以走循环，自己实现，都可以。

---

leetcode 137. 只出现一次的数字 ||

审题：只用一个数字出现一次，其余的数字都出现三次。
举例：[2,2,2,3]

如果只有[2,2,2]，那么统计结果就是0 3 0，这三个数都是可以整除3的。
因为有了[3]的加入，导致统计结果为0 4 1，可以发现第一位是可以整除3，后两位都不能整除3。那么可以得出结论：
出现一次的数 它的某个 位上是0不会影响统计结果，某个 位上是1，会影响结果(和无法整除3)。

推广：如果是：每个数都出现4次，只有一个数出现1次，和上面一样统计每个位1的总和，如果那个位上总和不能整除4，说明只出现一次的数在那个位上为1；如果依旧可以整除4，那么只出现一次的数在那个位上为0。

题解：

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int n=0;
        for(size_t i=0;i<32;i++)
        {
            int total=0;
            //遍历所有nums的第i位
            for(int num:nums)
            {
                total+=(num>>i&1);
            }
            //无法整除3的位，是1。
            if(total%3)
            {
                n=n|1<<i;
            }
        }
        return n;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

代码解释：

total+=(num>>i&1);
1

num取得是nums其中一个数，num向右移动i位，如果和1按位与结果为1，那么说明num的第i位为1。

           if(total%3)
            {
                n=n|1<<i;
            }
1
2
3
4

如果某个位1的和，无法整除3，那么那个位上是1对于只出现一次的数。
使1向左移动i位，再和n按位或，那么肯定会使n的第i位变成1。

就是这样，没毛病。

---

leetcode 260.只出现一次的数字 |||

审题：只有两个元素只出现一次，其余的都出现两次，要求返回一个数组，数组里有这两个元素，不在意两个元素的次序。
举例：[1,1,2,2,3,5]
用位运算可以解，这道题最简单的是用map来做，统计一下每个元素出现的次数，为1的就是我们要找到。这样做比较简单不讲，我们主要来看看用位运算如何做，也就是进阶版。

思路：
依旧先用0和数组的每个数进行异或，那么得到结果就是只出现一次的两个数的异或，这就需要我们想办法将这两个数分开。
用0去异或[1,1,2,2,3,5]，得到[3,5]两数的异或结果n。

n=110，n这个数，二进制位为1的时候说明一个问题：3和5在这个位上是不同的。也就是说：我们可不可以根据这个位·为0/为1，来将数组分成两派。那么3和5必然会被分成两派。对于上面的数组可以分成[115] [223]。[115]的第一位是0，[223]的第一位是1。分成两派就好搞了。这不就是分开的第一题嘛？直接对每一派都用0去异或就可以分别得到只出现一次的数字。
我们要去找n这个数的二进制位第一次为1的位，依此来分派。
题解：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        //得到只出现一次得两数的异或结果
        int n = 0;
        for (int num: nums) {
            n ^= num;
        }
        // 防止溢出
        //lsb就是n第一次位为1的位置
        int lsb = (n == INT_MIN ? n : n & (-n));
        int type1 = 0, type2 = 0;
        for (int num: nums) {
            if (num & lsb) {
                type1 ^= num;
            }
            else {
                type2 ^= num;
            }
        }
        vector<int> arr;
        arr.push_back(type1);
        arr.push_back(type2);
        return arr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

代码解释：

int lsb = (n == INT_MIN ? n : n & (-n));
1

可以用n=110来举例,n=6,-n=-6，两者按位与

可以看到n第一次位为1的位完美，展现出来了。然后可以据此分派。

            if (num & lsb) {
                type1 ^= num;
            }
            else {
                type2 ^= num;
1
2
3
4
5

如果num&lsb==1，说明在那位上为1，如果按位与结果是0，说明那位上为0。
两派分别异或，最终得到结果。

---