剑指 Offer 56 - II. 数组中数字出现的次数 II 【位运算】

淩亂°似流年 2022-11-06 03:54 198阅读 0赞

**统计32个bit位上1出现的次数，次数对三取余就是出现一次那个数字对应比特位的数**

class Solution { 
    public:
        int singleNumber(vector<int>& n) { 
            vector<int> c(32,0);
            for(int j=0;j<n.size();j++){ 
                for(int i=0;i<=31;i++){ 
                    if( (n[j] &(1<<i)) ){ 
                        c[i]++;
                    }
                }
            }
            int ret = 0;
            for(int i=31;i>=0;i--){ 
                ret *= 2;
                if(c[i]%3==1){ 
                    ret += 1;
                }
            }
            return ret;
        }
    };

![在这里插入图片描述][20210307211516608.png]

**有限状态机**

借用官方题解的图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]  
[出处][Link 1]侵删  
[https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/][Link 1]

> 还有一种更新one的方法：  
> 就是当n和two都是1的时候，one是0  
> 其他情况是 n^one  
> one = (n^one) & (~(n&two));  
> two更新类似

class Solution { 
    public:
        int singleNumber(vector<int>& ns) { 
            
            int one=0;
            int two=0;
            for(int n:ns){ 
                one = (n^one) & (~(n&two));
                two = (n^two) &( ~(n&one) );
            }
            return one;
        }
    };

![在这里插入图片描述][2021030721482495.png]

[20210307211516608.png]: /images/20221023/ab9acaa1c3444e2f92de36d30d2552f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20221023/308f528e9b6b4ebc879b12093835e5a1.png
[Link 1]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/
[2021030721482495.png]: /images/20221023/c42c0e2ae667412ebb294bf578b9a482.png