まず非反復ストリーム内の文字

Question

私の答えはあるが、私はこのコードを使用することができますし、何が複雑になるかどうかを知りたい：あなたかどうかについての

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); 
    } 
} 

Answer 1

あなたの疑問「このコードを使用することができます」少しあいまいです - あなたはそれを書いた場合、私はあなたがそれを使用することができると思うだろう:)

が

複雑さのためとして、それはnはStringの文字数があるO(n)あります。オカレンスの数をカウントするには、String全体を繰り返し処理し、最初のものを見つけるためにもう一度繰り返します（カウント数が1）。最悪の場合、非繰り返し文字はありません。または、反復文字だけが最後の文字です。どちらの場合も、もう一度String全体を反復処理する必要があります。したがって、それはO(n+n) = O(n)です。

EDIT

方法によって、あなたのコードにバグがあります。 の挿入注文LinkedHashMapを使用しているため、put(Character,Integer)を呼び出すたびに、下位のリストの並べ替えが行われます。代わりにLinkedHashMap<Character,int[]>を使用し、配置する前にキーの存在を確認する必要があります。存在する場合は、int[]に格納されている値をインクリメントするだけで、別のputコールを行うことでマップの再読み込みを避けることができます。それでも、結果のリストは反復する順番と逆順になるので、最初のの反復しない文字は、値が1である反復するときに最後に見つかるものになります。あなたの最初のforループの逆の場合、最初の非繰り返し文字が元の文字の最後の文字よりも早く到着する場合は、常にEntryセット全体を通過する必要はありません。String