面试题 50. 第一个只出现一次的字符

题目描述

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

示例 1:

输入：s = "abaccdeff"
输出：'b'

示例 2:

输入：s = "" 
输出：' '

限制：

0 <= s 的长度 <= 50000

解法

方法一：数组或哈希表

我们可以使用哈希表或数组来统计每个字符出现的次数，然后再遍历一遍字符串，找到第一个出现次数为 $1$ 的字符。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为字符串长度；而 $C$ 为字符集大小，本题中 $C=26$。

Python3JavaC++GoTypeScriptRustJavaScriptC#

class Solution:
    def firstUniqChar(self, s: str) -> str:
        cnt = Counter(s)
        for c in s:
            if cnt[c] == 1:
                return c
        return " "

class Solution {
    public char firstUniqChar(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (cnt[c - 'a'] == 1) {
                return c;
            }
        }
        return ' ';
    }
}

class Solution {
public:
    char firstUniqChar(string s) {
        int cnt[26]{};
        for (char& c : s) {
            ++cnt[c - 'a'];
        }
        for (char& c : s) {
            if (cnt[c - 'a'] == 1) {
                return c;
            }
        }
        return ' ';
    }
};

func firstUniqChar(s string) byte {
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
    }
    for _, c := range s {
        if cnt[c-'a'] == 1 {
            return byte(c)
        }
    }
    return ' '
}

function firstUniqChar(s: string): string {
    const map = new Map();
    for (const c of s) {
        map.set(c, !map.has(c));
    }
    for (const c of s) {
        if (map.get(c)) {
            return c;
        }
    }
    return ' ';
}

use std::collections::HashMap;
impl Solution {
    pub fn first_uniq_char(s: String) -> char {
        let mut map = HashMap::new();
        for c in s.as_bytes() {
            map.insert(c, !map.contains_key(c));
        }
        for c in s.as_bytes() {
            if map[c] {
                return char::from(*c);
            }
        }
        ' '
    }
}

/**
 * @param {string} s
 * @return {character}
 */
var firstUniqChar = function (s) {
    const cnt = new Array(26).fill(0);
    for (const c of s) {
        cnt[c.charCodeAt(0) - 97]++;
    }
    for (const c of s) {
        if (cnt[c.charCodeAt(0) - 97] === 1) {
            return c;
        }
    }
    return ' ';
};

public class Solution {
    public char FirstUniqChar(string s) {
        var cnt = new int[26];
        foreach(var c in s) {
            cnt[c - 'a'] ++;
        }
        foreach(var c in s) {
            if (cnt[c - 'a'] == 1) {
                return c;
            }
        }
        return ' ';
    }
}

面试题 50. 第一个只出现一次的字符

题目描述

解法

方法一：数组或哈希表

评论