劍指 offer 面試題 50 第一個只出現一次的字元（有序雜湊表O(n)）

第一個只出現一次的字元

個人部落格

---

在字串 s 中找出第一個只出現一次的字元。如果沒有，返回一個單空格。 s 只包含小寫字母。

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

題解

• 雜湊表法

  • 演算法思想
    • 利用空間換時間，達到在 O(1)時間內找到字元之前是否存在字串中的目的
  • 複雜度分析
    • 時間複雜度 O(n)：遍歷兩邊字串
    • 空間複雜度 O(1)：其實可以算 O(1)，因爲字元數量不會隨着 n 增長而增長

  class Solution {
      public char firstUniqChar(String s) {
          HashMap<Character,Boolean> map = new HashMap<>();
          for(int i = 0;i < s.length(); i++){
            	//這裏的想法很巧妙，第一次插入就是 true，否則是 false
              map.put(s.charAt(i),!map.containsKey(s.charAt(i)));
          }
          for(int i = 0;i < s.length();i++){
              if(map.get(s.charAt(i)))return s.charAt(i);
          }
          return ' ';
      }
  }
  

• 有序雜湊表

  • 演算法思想
    • 使用有序雜湊表，有序雜湊表中的鍵值對是按照插入順序排序的
    • 第二次遍歷的時候取出第一個爲 true 的就行了

  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 ' ';
      }
  }
  

  此程式碼複製貼上大佬的程式碼。

總結

• 雜湊表是個好東西
• 字元可以做個索引，當自制 自製雜湊表的時候可以想到字元’