確定字符串中是否有字符出現在K次

我所做的是做一個嵌套循環，達到O(n^2)時間。我的問題是，如果有更好的解決方案可以減少時間複雜性？確定字符串中是否有字符出現在K次

2015-12-20 Zongyang

抽象方法：將字符串縮減爲直方圖。掃描直方圖以查找頻率爲3的條目。鍵是出現三次的字符。 – Kaz

是的，這可以在O(n)完成。你只需要散列所有字符（甚至可以是數組）。當你迭代你的字符串時，你增加你找到的字符的數量。

然後在最後迭代你的散列並輸出所有的鍵值，它們的值等於k。

和Python中的快速幾行

def func(s, k): 
    from collections import Counter 
    h = Counter(s) 
    return [i for i in h if h[i] == k]

這將返回字符串s在發生k次的所有字符。

2015-12-20 04:56:13

謝謝薩爾瓦多。但是如果我保留一個散列表，我需要檢查每個迭代元素是否已經存在，所以每次迭代都有一個O（logN）時間，總運行時間爲O（NlogN），對嗎？ – Zongyang

@Zongyang請仔細閱讀基本數據結構的時間複雜度，你在hash中的搜索是'O（1）'。 –

回答