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

题目描述

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

示例 1:

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

示例 2:

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

限制：

0 <= s 的长度 <= 50000

解法

方法一：数组或哈希表

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

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

Python3JavaC++GoTypeScriptRustJavaScriptC#Swift

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 cnt: number[] = 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 ' ';
}

impl Solution {
    pub fn first_uniq_char(s: String) -> char {
        let mut cnt = [0; 26];
        for c in s.chars() {
            cnt[(c as usize) - ('a' as usize)] += 1;
        }
        for c in s.chars() {
            if cnt[(c as usize) - ('a' as usize)] == 1 {
                return c;
            }
        }
        ' '
    }
}

/**
 * @param {string} s
 * @return {character}
 */
var firstUniqChar = function (s) {
    const cnt = 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 ' ';
    }
}

class Solution {
    func firstUniqChar(_ s: String) -> Character {
        var count = [Int](repeating: 0, count: 26)
        let aAsciiValue = Int(Character("a").asciiValue!)

        for char in s {
            count[Int(char.asciiValue!) - aAsciiValue] += 1
        }

        for char in s {
            if count[Int(char.asciiValue!) - aAsciiValue] == 1 {
                return char
            }
        }

        return " "
    }
}

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

题目描述

解法

方法一：数组或哈希表

评论