剑指offer Hash

剑指offer-第一个只出现一次的字符

Posted by franki on May 10, 2021

第一个只出现一次的字符

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

示例

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

思路

利用空间换时间的思路，采用hash记录每个字符出现的次数，接着遍历一遍即可知道第一个出现一次的字符

代码

/**
 * @param {string} s
 * @return {character}
 */
var firstUniqChar = function(s) {
    const hash = {};

    for (let str of s) {
        if (!hash[str]) {
            hash[str] = 1;
        } else {
            hash[str]++;
        }
    }

    for (let key in hash) {
        if (hash[key] === 1) {
            return key;
        }
    }

    return " ";
};

复杂度分析

时间复杂度: O(N)
空间复杂度: O(N)