Go Java算法之字符串中第一個(gè)唯一字符詳解

更新時(shí)間：2022年08月24日 10:11:43 作者：黃丫丫

這篇文章主要為大家介紹了Go Java算法之字符串中第一個(gè)唯一字符詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

字符串中第一個(gè)唯一字符

給定一個(gè)字符串 s ，找到它的第一個(gè)不重復(fù)的字符，并返回它的索引。如果不存在，則返回 -1 。

示例 1：

輸入: s = "leetcode"

輸出: 0

示例 2:

輸入: s = "loveleetcode"

輸出: 2

示例 3:

輸入: s = "aabb"

輸出: -1

提示:

1 <= s.length <= 105

s 只包含小寫字母

方法一：哈希表（Java）

在第一次遍歷時(shí)，我們使用哈希映射統(tǒng)計(jì)出字符串中每個(gè)字符出現(xiàn)的次數(shù)。

在第二次遍歷時(shí)，我們只要遍歷到了一個(gè)只出現(xiàn)一次的字符，那么就返回它的索引，否則在遍歷結(jié)束后返回 -1。

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：字符串長(zhǎng)度

Σ：字符集

時(shí)間復(fù)雜度：O（n）

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

方法二：隊(duì)列（Go）

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

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

當(dāng)我們對(duì)字符串進(jìn)行遍歷時(shí)，設(shè)當(dāng)前遍歷到的字符為 c，如果 c 不在哈希映射中，我們就將 c 與它的索引作為一個(gè)二元組放入隊(duì)尾

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

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：字符串長(zhǎng)度

Σ：字符集

時(shí)間復(fù)雜度：O（n）

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

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

您可能感興趣的文章: