当前位置：网站首页>只出现一次的数字 II（哈希、位操作、逻辑电路、有限状态自动机）

只出现一次的数字 II（哈希、位操作、逻辑电路、有限状态自动机）

2022-04-21 12:17:00 【4nc414g0n】

只出现一次的数字 II

题目链接
题目描述：
给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素

方法1：哈希

思路：

建立一个数字用来映射次数

遍历拿出次数次数为1的

方法2：位操作

思路：

以[2,2,3,2]为例：
由于其他数都是3个，把每个数的每个位二进制的之和填入32个元素的数组
遍历%3，得到的就是那个数

代码如下：

class Solution {
     
public:
   int singleNumber(vector<int>& nums) {
        
       vector<int> bit_arr(32,0);
       for(int i=0;i<nums.size();i++)
       {
     
           int bit=32;
           while(bit--)
           {
     
               bit_arr[bit]+= (1&(nums[i]>>bit));
           }
       }

       int ret=0;
       for(int i=0;i<32;i++)
       {
     
           if(bit_arr[i]%3==1)
           {
     
               ret|=(1<<i);//例如左移3位 0000001000，按位或达到效果
           }
       }
       return ret;
   }
};