溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

LeetCode如何找出第一個只出現一次的字符

發(fā)布時間：2021-12-15 14:08:31 來源：億速云 閱讀：140 作者：小新 欄目：大數據

小編給大家分享一下LeetCode如何找出第一個只出現一次的字符，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

題目描述

在字符串 s 中找出第一個只出現一次的字符。如果沒有，返回一個單空格。s 只包含小寫字母。

0 <= s 的長度 <= 50000

               

題目樣例

               

示例

  • s = "abaccdeff"

  • 返回 "b"

  • s = ""

  • 返回 " "

               

題目思考

  1. 如何遍歷一遍字符串就得到結果?
               

解決方案

               
思路
  • 一個比較容易想到的思路是使用一個計數字典, 遍歷一遍字符串存每個字符的數目, 然后把數目為 1 的字符單獨放在集合中, 再從頭遍歷一遍字符串, 找第一個在集合中的字符, 沒有的話就返回' '
  • 但這種做法需要遍歷兩遍字符串, 效率不高, 如何做到只遍歷一遍字符串就得到結果呢?
  • 重新思考, 如果我們遍歷的過程中額外存第一個下標, 然后后續(xù)遇到該字符時只更新計數, 這樣是不是就無需再次遍歷了呢?
  • 也就是說, 將計數字典改造為 c => [firstIndex, cnt] 這樣的 kv 組合, 最后只需要找 cnt==1 且 firstIndex 最小的 c 即可
               
復雜度
  • 時間復雜度 O(N+C): 只需要遍歷一遍字符串, 之后遍歷字典的復雜度為 O(C) (C 是字符種類數, 常數 26)
  • 空間復雜度 O(C): 使用了一個字典, 存 C 個 kv
               
代碼
class Solution:
    def firstUniqChar(self, s: str) -> str:
        # 字典存c => [firstIndex, cnt]
        # 這樣只需要遍歷一遍字符串
        d = {}
        for i, c in enumerate(s):
            if c in d:
                # 只更新cnt
                d[c][1] += 1
            else:
                d[c] = [i, 1]
        res = ' '
        # 初始化最小下標為字符串長度, 有效下標肯定都小于它
        mnIndex = len(s)
        for c in d:
            firstIndex, cnt = d[c]
            if cnt == 1 and firstIndex < mnIndex:
                mnIndex = firstIndex
                res = c
        return res

以上是“LeetCode如何找出第一個只出現一次的字符”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業(yè)資訊頻道！

向AI問一下細節(jié)

免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。

AI
助
手