第一个只出现一次的字符

---

题目：

题解：

1、使用哈希表存储

• 解题思路：

  • 遍历字符串 s ，使用哈希表统计 “各字符数量是否 >1 ”。
  • 再遍历字符串 s ，在哈希表中找到首个 “数量为 1 的字符”，并返回。

• 复杂度分析：

  • 时间复杂度 O(N) ： N 为字符串 s 的长度；需遍历 s 两轮，使用 O(N) ；HashMap 查找操作的复杂度为 O(1)；
  • 空间复杂度 O(1) ： 由于题目指出 s 只包含小写字母，因此最多有 26 个不同字符，HashMap 存储需占用 O(26) = O(1) 的额外空间。

• 代码：

  class Solution2 {
      public char firstUniqChar(String s) {
          HashMap<Character, Boolean> map = new HashMap<>();
          char[] array = s.toCharArray();
          for (char c:
               array) {
              // 如果遇到重复的，value变为false
              map.put(c,!map.containsKey(c));
  
          }
          // 在map中查找第一个为true的
          // 因为hashMap是乱序的，不能直接通过map查找到第一个，而是通过array原来的顺序，进行map查找
          for (char c:
               array) {
              if (map.get(c)) {
                  return c;
              }
          }
          return ' ';
      }
  }

2、有序哈希表

在字符串长度较大、重复字符很多时，“有序哈希表” 解法理论上效率更高。

解题思路和时间复杂度一样。

代码：

// 有序哈希表
class Solution3 {
    public char firstUniqChar(String s) {
        Map<Character, Boolean> map = new LinkedHashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            map.put(c, !map.containsKey(c));
        // Map的entrySet()方法返回一个实现Map.Entry接口的对象集合。Map.Entry里面包含getKey()和getValue()方法,entrySet实现了Set接口，里面存放的是键值对。一个K对应一个V。
        for(Map.Entry<Character, Boolean> d : map.entrySet()){
            if(d.getValue()) return d.getKey();
        }
        return ' ';
    }
}