2 回答

TA貢獻1799條經驗 獲得超9個贊
除了奧萊的回答,你還需要考慮一些“微”優化:
我懷疑大部分時間都會花在執行這個循環上:
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()
創建一個子字符串,以便它可以計算出它的長度。但是我們知道那個長度是多少:qq
!qq
因此,您無緣無故地創建了一個新字符串并復制了字符。效率低下。無意義。s.substring(0,(qq-1)).charAt(k)==someChar
創建另一個字符串,然后獲取它的k
第 th 個字符。但是k
子字符串的第 th 個字符也是k
原始字符串的第 th 個字符s
。(想想看?。┧?,再一次創建子串是沒有意義的。那些不必要的計算都重復了
qq
多次。這是相同的(不必要的)計算完成2 x qq
時間。
注意:此分析不考慮您的代碼是否正確或算法是否最優。這純粹是關于微觀效率。你所做的是將O(N^2)
算法變成O(N^3)
算法......由于不必要的子字符串創建。

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