数据结构学习 jz56数组中数字出现的次数

关键词：位运算 异或性质

虽然有两道题，但是其实应该分成三个级别的题目。

题目一：

一个整型数组?sockets?里除?一个?数字之外，其他数字都出现了两次。

思路：异或的性质

?复杂度计算：

时间复杂度O(n)

空间复杂度O(1)

代码：

遍历一次，全部求异或，就可以得到 没有成双成对的那个数字。

vector<int> singleNumber(vector<int>& sockets) {
    int x = 0;
    for(int num : sockets)  // 1. 遍历 sockets 执行异或运算
        x ^= num;
    return x;            // 2. 返回出现一次的数字 x
}

题目二：

?和题目一不一样的是 有两个不成对的数字。

思路：

用题目一的方法是无法完成的。

可以将两个我们需要找到的数进行分区，再进行查找。

步骤：

1. 第一次遍历：异或所有数。找到两个数的异或：n=A^B
2. 循环左移，找到n里面最低位的1的位置，比如n为10100，那么m为00100。因为n里为1的部位意味着A和B不一样的部分，可以根据这个不一样的部分进行分区。
3. 第二次遍历：利用socket&m的结果进行分区，分为两个区，两个区分别进行和题目一一样的异或，分别找到A和B。

循环左移的详细依据，如果看不懂可以仔细看这个：

?复杂度计算：

时间复杂度O(n)

空间复杂度O(1)

代码：

class Solution {
public:
    vector<int> sockCollocation(vector<int>& sockets) {
        int n=0,m=1;
        for(const auto&socket:sockets)//第一次遍历：找到两个不一样的数的异或
        {
            n^=socket;
        }//n的结果就是x^y
        while((n&m)==0)//循环左移，找到n里最低的1
        {//比如：n:010100 那么m:000100
            m<<=1;
        }
        int x=0,y=0;//存结果
        for(const auto&socket:sockets)//第二次遍历：分组，找到两个不一样的数
        {//将sockets分为两组，一组是可以和m与之后等于1的，另一组和m与之后等于0
            if(socket&m) x^=socket;
            else y^=socket;
        }
        return {x,y};
    }
};

题目三：

思路：

考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。
因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。

复杂度计算：

时间复杂度O(n)

空间复杂度O(1)

代码：

class Solution {
public:
    int trainingPlan(std::vector<int>& actions) {
        std::vector<int> count(32);
        for (int action : actions)
        {
            // 不能用while(action) 
            // 因为负数会出错：
            // 比如-1的补码：11...111
            // 如果右移，左边还是会补1
            // 就会一直是-1，while就不会停止循环
            for(int i=0;i<32;++i)
            {
                count[i] += action & 1;
                action = action >> 1;
            }
        }
        int res = 0;
        for (int i = 31; i >= 0; --i)
        {
            res = res << 1;
            res |= count[i] % 3;
        }
        return res;
    }
};