第一個非重複的字符

我要回答的問題是這樣的，但我想知道如果我可以使用此代碼，會是怎樣的複雜性：第一個非重複的字符

import java.util.LinkedHashMap; 
import java.util.Map.Entry; 

public class FirstNonRepeatingCharacterinAString { 

    private char firstNonRepeatingCharacter(String str) {  
     LinkedHashMap<Character, Integer> hash = 
       new LinkedHashMap<Character, Integer>(); 

     for(int i = 0 ; i< str.length() ; i++) 
     { 
      if(hash.get(str.charAt(i))==null) 
       hash.put(str.charAt(i), 1); 
      else 
       hash.put(str.charAt(i), hash.get(str.charAt(i))+1); 
     } 

     System.out.println(hash.toString()); 

     for(Entry<Character, Integer> c : hash.entrySet()) 
     { 
      if(c.getValue() == 1) 
       return c.getKey(); 
     } 

     return 0 ; 
    } 

    public static void main(String args[]) 
    { 
     String str = "geeksforgeeks"; 
     FirstNonRepeatingCharacterinAString obj = 
       new FirstNonRepeatingCharacterinAString(); 
     char c = obj.firstNonRepeatingCharacter(str); 
     System.out.println(c); 
    } 
}

來源

2017-05-09 DavidB

*我想知道我是否可以使用此代碼。*這是版權問題嗎？ – shmosel

這段代碼的複雜性是O（n）。但是你的代碼似乎沒有返回標題中提到的內容。 – arunk2

我只是想知道，如果這個解決方案有效。它不是一個版權問題。 – DavidB

你有關的問題是否你「可以使用此代碼」是一個小曖昧 - 如果你寫的，我還以爲你可以用它:)

至於複雜性，這是O(n)其中n是在String的字符數。要計算出現次數，您必須遍歷整個String，再次迭代它們以找到計數爲1的第一個。在最糟糕的情況下，您沒有非重複字符，或者唯一不重複的字符是最後一個字符。無論哪種情況，您都必須重複遍歷整個String。所以它是O(n+n) = O(n)。

編輯

。在你的代碼中的錯誤，順便說一句。由於您正在使用插入訂單LinkedHashMap，因此每次調用put(Character,Integer)都會導致對基礎列表進行重新排序。您應該使用LinkedHashMap<Character,int[]>來替代，並且在放置之前檢查密鑰的存在。如果它們存在，那麼只需增加存儲在int[]中的值，以避免通過撥打另一個put呼叫來重新定位地圖。即使如此，結果列表的排列方式也會與您遍歷它的方式相反，因此非重複字符將是迭代其值時爲1的最後一個字符。或者，您也可以迭代在第一個for循環中相反，那麼如果第一個非重複字符比最初的String中的最後一個字符快，則您不必總是遍歷整個Entry集合。

來源

2017-05-09 23:48:51 CodeBlind

第一個非重複的字符

回答

相關問題