数组中数字出现的次数II

Map记录数字出现的次数

代码

   /**
     *  HashMap 集合
     *  23ms
     */
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int num:nums){
            if(map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else{
                map.put(num,1);
            }
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()==1){
                return entry.getKey();
            }
        }
        return 0;
    }

遍历统计每一位

思路

• 在数字的二进制形式下，对于出现三次的数字，各二进制位出现的次数都是3的倍数。

• 统计所有数字的各个二进制中1的出现的次数，对3求余，结果则为只出现一次的数字

  • 详细思路如下：

    
    

• 时间复杂度 O(N) ：其中 N位数组 nums的长度；遍历数组占用 O(N) ，每轮中的常数个位运算操作占用 O(1)

• 空间复杂度 O(1)

• 修改求余数值m，即可解决除了一个数字以外，其他数字都出现m次的通用问题。

代码

 /*
  * 5ms
  */
   public int singleNumber3(int[] nums) {
       int[] counts=new int[32];
       for(int num:nums){
           for(int j=0;j<32;j++){ //从低位往高位统计
               counts[j]+=num&1;
               num>>>=1;  //无符号右移
           }
       }
       int res=0,m=3;
       for(int i=0;i<32;i++){
           res<<=1; //左移 从高位往低位“累加”
           res|=counts[31-i]%m;  
       }
       return res;
    }

参考 位运算 + 有限状态自动机，清晰图解

---

状态机

​ 原文链接：

​ 状态机解决此问题详解 （数字电路）