题目描述

在字符串中找出第一个只出现一次的字符。

如输入”abaccdeff”，则输出b。

如果字符串中不存在只出现一次的字符，返回 # 字符。

样例

输入："abaccdeff"

输出：'b'

算法

找不同的题目，需要将每个元素都遍历一遍 ，如果不能遍历整个string 我们是无法找出不同的，因此时间复杂度至少是O(N)

开辟一个map 以string 中的字符作为key值 以出现的次数作为valus 遍历到一次 就加1.

时间复杂度

O(N)

C++ 代码

class Solution {
public:
    char firstNotRepeatingChar(string s) {

      unordered_map<char,int > count;//开辟一个unordered_map 注意其元素的类型
      for(auto c:s)count[c]++;//遍历整个数组
      for(auto x:s)
      if(count[x]==1) return x;//查找对应的value值 找到其中等于1的，取出对应的char
      return '#';
    }
};

java代码

class Solution {
    public char firstUniqChar(String s) {
        //从头至尾遍历每个字符，用一个Map存好，key为字符，value为出现的次数
        if(s == null || s.length() == 0) return '#';
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0;i < s.length();i++){
            map.merge(s.charAt(i),1,Integer::sum);//merge的用法尤其要掌握
            //如果键原先不存在，将把word与1关联，否则使用Integer.sum函数组合原值和1（也就是将原值与1求和）
        }
        for(int i = 0;i < s.length();i++){
            if(map.get(s.charAt(i)) == 1){
                return s.charAt(i);
            }
        }
        return '#';//注意是单引号
    }
}