[剑指offer]面试题第[50]题[JAVA][第一个只出现一次的字符][哈希表][HashMap]

- 日理万妓 2023-02-21 06:32 75阅读 0赞

#### 【问题描述】\[简单\] ####

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
    
    示例:
    
    s = "abaccdeff"
    返回 "b"
    
    s = "" 
    返回 " "

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

###### 1. 哈希表 ######

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

class Solution { 
        public char firstUniqChar(String s) { 
            HashMap<Character, Boolean> dic = new HashMap<>();
            char[] sc = s.toCharArray();
            for(char c : sc)
                dic.put(c, !dic.containsKey(c));
            for(char c : sc)
                if(dic.get(c)) return c;
            return ' ';
        }
    }

###### 2. 有序哈希表 ######

![在这里插入图片描述][20200629115651252.png]  
**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][20200629115705307.png]

class Solution { 
        public char firstUniqChar(String s) { 
            Map<Character, Boolean> dic = new LinkedHashMap<>();
            char[] sc = s.toCharArray();
            for(char c : sc)
                dic.put(c, !dic.containsKey(c));
            for(Map.Entry<Character, Boolean> d : dic.entrySet()){ 
               if(d.getValue()) return d.getKey();
            }
            return ' ';
        }
    }

###### 3. 使用数组代替哈希表计数 ######

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

public class firstUniqChar { 
        public char firstUniqChar(String s) { 
            int[] count = new int[256];
            char[] chars = s.toCharArray();
            for(char c : chars)
                count[c]++;
            for(char c : chars){ 
                if(count[c] == 1)
                    return c;
            }
            return ' ';
        }
    }

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

###### 1. HashMap HashSet 去重题目优先考虑 / 新建字符数组统计数量 ######

###### 2.遍历 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);
        }
        }

转载链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/solution/mian-shi-ti-50-di-yi-ge-zhi-chu-xian-yi-ci-de-zi-3/

参考链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/solution/mian-shi-ti-50java-shi-yong-shu-zu-dai-ti-ha-xi-bi/

参考链接：https://segmentfault.com/a/1190000012712443

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629115421906.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200629115441828.png]: https://img-blog.csdnimg.cn/20200629115441828.png
[20200629115651252.png]: https://img-blog.csdnimg.cn/20200629115651252.png
[20200629115705307.png]: https://img-blog.csdnimg.cn/20200629115705307.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200629120743297.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70