[剑指offer]面试题第[56-2]题[JAVA][数组中数字出现的次数][状态机][hashmap][位运算]

末蓝、 2023-02-22 13:56 58阅读 0赞

#### 【问题描述】\[中等\] ####

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
    
     
    
    示例 1：
    
    输入：nums = [3,4,3,3]
    输出：4
    示例 2：
    
    输入：nums = [9,1,7,9,7,9,7]
    输出：1
     
    
    限制：
    
    1 <= nums.length <= 10000
    1 <= nums[i] < 2^31

#### 【解答思路】 ####

###### 1. HashMap ######

**时间复杂度：O(N) 空间复杂度：O(1)**

public int singleNumber(int[] nums) { 
            HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for (int n : nums) { 
            if (map.containsKey(n)) { 
                map.put(n,map.get(n)+1);
            } else { 
                map.put(n,1);
            }
        }
       
        int i = 0;
        // for(int n : map.keySet()) { 
        // if(map.get(n)==1)
        // return n;
        // }
        for(Map.Entry<Integer,Integer> d:map.entrySet()){ 
            if(d.getValue()==1)
                return d.getKey();
        }
        return -1;
        }

二三解题思路  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

###### 2. 有限状态自动机 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
**时间复杂度：O(N) 空间复杂度：O(1)**  
![在这里插入图片描述][20200704120720898.png]

class Solution { 
        public int singleNumber(int[] nums) { 
            int ones = 0, twos = 0;
            for(int num : nums){ 
                ones = ones ^ num & ~twos;
                twos = twos ^ num & ~ones;
            }
            return ones;
        }
    }

###### 3. 遍历统计 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
**时间复杂度：O(N) 空间复杂度：O(1)**  
![在这里插入图片描述][20200704120943502.png]  
![在这里插入图片描述][20200704120921643.png]

class Solution { 
        public int singleNumber(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;
        }
    }

#### 【总结】 ####

###### 1.遍历 HashMap 四种方法 ######

public static void main(String[] args) { 
    Map<String,String> map=new HashMap<String,String>();
        map.put("1", "value1");
        map.put("2", "value2");
        map.put("3", "value3");
        map.put("4", "value4");
        
        //第一种：普通使用，二次取值(性能差)
        System.out.println("\n通过Map.keySet遍历key和value：");  
        for(String key:map.keySet())
        { 
         System.out.println("Key: "+key+" Value: "+map.get(key));
        }
        
        //第二种(性能比第一种好，一次取值)
        System.out.println("\n通过Map.entrySet使用iterator遍历key和value: ");  
        Iterator map1it=map.entrySet().iterator();
        while(map1it.hasNext())
        { 
         Map.Entry<String, String> entry=(Entry<String, String>) map1it.next();
         System.out.println("Key: "+entry.getKey()+" Value: "+entry.getValue());
        }
        
        //第三种：推荐，尤其是容量大时 
        System.out.println("\n通过Map.entrySet遍历key和value");  
        for(Map.Entry<String, String> entry: map.entrySet())
        { 
         System.out.println("Key: "+ entry.getKey()+ " Value: "+entry.getValue());
        }
        
        //第四种 
        System.out.println("\n通过Map.values()遍历所有的value，但不能遍历key");  
        for(String v:map.values())
        { 
         System.out.println("The value is "+v);
        }
        }

###### 2.状态机 数电 设计逻辑电路的状态转换图 ######

###### 3.个人认为掌握方法一 HashMap和 方法三 统计遍历 足够了 ，有数电或对状态机感兴趣的可以使用方法二 ######

位运算 判相等异或^ 取位与&1 置位或|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/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200704120425822.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200704120556403.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200704120700536.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200704120710492.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200704120720898.png]: https://img-blog.csdnimg.cn/20200704120720898.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200704120850521.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200704120943502.png]: https://img-blog.csdnimg.cn/20200704120943502.png
[20200704120921643.png]: https://img-blog.csdnimg.cn/20200704120921643.png