class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}

n：字符串長度

Σ：字符集

時間復雜度：O（n）

空間復雜度：O(∣Σ∣)

方法二：隊列（Go）

我們也可以借助隊列找到第一個不重復的字符。隊列具有「先進先出」的性質(zhì)，因此很適合用來找出第一個滿足某個條件的元素。

具體地，我們使用與方法二相同的哈希映射，并且使用一個額外的隊列，按照順序存儲每一個字符以及它們第一次出現(xiàn)的位置。

當我們對字符串進行遍歷時，設當前遍歷到的字符為 c，如果 c 不在哈希映射中，我們就將 c 與它的索引作為一個二元組放入隊尾

否則我們就需要檢查隊列中的元素是否都滿足「只出現(xiàn)一次」的要求，即我們不斷地根據(jù)哈希映射中存儲的值（是否為 -1）選擇彈出隊首的元素，直到隊首元素「真的」只出現(xiàn)了一次或者隊列為空。

type pair struct {
    ch  byte
    pos int
}
func firstUniqChar(s string) int {
    n := len(s)
    pos := [26]int{}
    for i := range pos[:] {
        pos[i] = n
    }
    q := []pair{}
    for i := range s {
        ch := s[i] - 'a'
        if pos[ch] == n {
            pos[ch] = i
            q = append(q, pair{ch, i})
        } else {
            pos[ch] = n + 1
            for len(q) > 0 && pos[q[0].ch] == n+1 {
                q = q[1:]
            }
        }
    }
    if len(q) > 0 {
        return q[0].pos
    }
    return -1
}

n：字符串長度

Σ：字符集

時間復雜度：O（n）

空間復雜度：O(∣Σ∣)

以上就是Go Java算法之字符串中第一個唯一字符詳解的詳細內(nèi)容，更多關于Go Java算法字符串唯一字符的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: