题目描述

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

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

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

样例

输入："abaccdeff"

输出：'b'

算法1

(multiset)

1. 一开始用的set，一直不对。然后想起来set会自动去重，改成multiset就AC了。

时间复杂度

$O(nlogn)$
一共有n个元素，multiset的增删改查一个元素的时度是$O(logn)$

C++ 代码

class Solution {
public:
    char firstNotRepeatingChar(string s) {
        if(s == "") return '#';

        multiset<char> se;

        for(auto c : s)
            se.insert(c);

        for(auto c : s)
            if(se.count(c) == 1)
                return c;
        return '#';
    }
};

算法2

(hash)

时间复杂度

$O(n)$
因为哈希的增删改查的时度是$O(1)$

C++ 代码

class Solution {
public:
    char firstNotRepeatingChar(string s) {
        if(s == "") return '#';

        unordered_map<char, int> um;
        for(auto c : s)
            um[c] ++;

        for(auto c : s)
            if(um[c] == 1)
                return c;
        return '#';
    }
};