2 回答

TA貢獻1799條經(jīng)驗 獲得超9個贊
除了奧萊的回答,你還需要考慮一些“微”優(yōu)化:
我懷疑大部分時間都會花在執(zhí)行這個循環(huán)上:
for(int k=0;k<s.substring(0,qq-1).length();k++){ if((s.substring(0,(qq-1)).charAt(k)==someChar)) count[j]++; }
讓我們看幾個方面:
k<s.substring(0,qq-1).length()
創(chuàng)建一個子字符串,以便它可以計算出它的長度。但是我們知道那個長度是多少:qq
!qq
因此,您無緣無故地創(chuàng)建了一個新字符串并復制了字符。效率低下。無意義。s.substring(0,(qq-1)).charAt(k)==someChar
創(chuàng)建另一個字符串,然后獲取它的k
第 th 個字符。但是k
子字符串的第 th 個字符也是k
原始字符串的第 th 個字符s
。(想想看?。┧裕僖淮蝿?chuàng)建子串是沒有意義的。那些不必要的計算都重復了
qq
多次。這是相同的(不必要的)計算完成2 x qq
時間。
注意:此分析不考慮您的代碼是否正確或算法是否最優(yōu)。這純粹是關(guān)于微觀效率。你所做的是將O(N^2)
算法變成O(N^3)
算法......由于不必要的子字符串創(chuàng)建。

TA貢獻1821條經(jīng)驗 獲得超6個贊
對于長字符串(最多 500000 個字母)和許多查詢(最多 10000 個)的有效解決方案,您需要以某種方式預(yù)處理字符串數(shù)據(jù),以便之后您可以快速處理每個查詢。我建議對于 26 個可能的小寫字母(問題明確表示“a”-“z”)中的每一個,找到第 1、2、3 次出現(xiàn)的位置等,并將它們填充到數(shù)組或列表中。然后對于每個查詢,在數(shù)組中進行二進制搜索以查找您作為輸入獲得的位置。然后找到的數(shù)組索引會告訴你答案。這會將您的時間復雜度從O(s^2 * q)降低到O(s + q * log(s))。
如果您不知道二進制搜索,請查找它?;蛘呤褂?aMap<Integer, Integer>
而不是數(shù)組或列表。
更高效的是,構(gòu)建一個與字符串長度相同的數(shù)組,并在每個索引中存儲關(guān)于該索引的查詢的答案。我相信這可以用復雜度O(s + q)來實現(xiàn)。
添加回答
舉報