なぜこのアルゴリズムはとても遅いのですか？

Question

文字列を指定すると、その中の最初の非繰り返し文字を見つけてインデックスを返します。存在しない場合は-1を返します。

S = "leetcode" リターン0

S = "loveleetcode"、 リターン2

これはシンプルで理解しやすい私のソリューションです。しかし、LeetCodeでは「時間が限界を超えています」という報告があります。これは遅すぎることを意味します。これはO（n^2）ソリューションです。

public int firstUniqChar(String s) { 

     if(s==null || s.isEmpty()){ 
      return -1; 
     } 
     if(s.length()==1){ 
      return 0; 
     } 

     char[] ss = s.toCharArray(); 

     int size = s.length(); 
     HashSet<Character> repeats = new HashSet<Character>(); 
     for(int i=0; i<size; i++){ 

      for(int j=i+1; j<size; j++){ 
       if(repeats.contains(ss[i])){ 
        continue; 
       } 
       if(ss[i]==ss[j]){ 
        repeats.add(ss[i]); 
        break; 
       } 
      } 

      if(!repeats.contains(ss[i])){ 
       return i; 
      } 
     } 
     return -1; 
    } 

しかし、別のバージョンは以下のように、「時間が制限を超えた」と判断されない、でも遅くなるようだ：

static int firstUniqChar(String s) { 

     if(s==null || s.isEmpty()){ 
      return -1; 
     } 
     if(s.length()==1){ 
      return 0; 
     } 

     char[] ss = s.toCharArray(); 

     int size = s.length(); 
     for(int i=0; i<size; i++){ 

      boolean unique = true; 
      for(int j=i+1; j<size; j++){ 
       if(ss[i]==ss[j]){ 
        unique = false; 
        break; 
       } 
      } 
      if(unique){ 
       for(int j=0; j<i; j++){ 
        if(ss[i]==ss[j]){ 
         unique = false; 
         break; 
        } 
       } 
      } 
      if(unique){ 
       return i; 
      } 
     } 
     return -1; 
    } 

Answer 1

内側のループをしないでください。時間の貿易空間と文字列をトラバースする際にユニークであるかどうかを追跡する1回。

public static int firstUniqChar(String s) { 

    if(s==null || s.isEmpty()){ 
     return -1; 
    } 
    if(s.length()==1){ 
     return 0; 
    } 


    Map<Character, Integer> uniqueCharacterMap = new LinkedHashMap<Character, Integer>(); 
    Set<Character> nonuniqueCharacterSet = new HashSet<Character>(); 

    for (int i=0; i<s.length();i++) { 
     Character c = s.charAt(i); 
     if (nonuniqueCharacterSet.contains(c)) { 
      // character has already been determined to repeat 
     } else if (uniqueCharacterMap.containsKey(c)) { 
      uniqueCharacterMap.remove(c); // It's not unique 
      nonuniqueCharacterSet.add(c); 
     } else { 
      // so far, it is unique. 
      uniqueCharacterMap.put(c, i); 
     } 
    } 

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

    Iterator<Map.Entry<Character, Integer>> i = uniqueCharacterMap.entrySet().iterator(); 
    if (i.hasNext()) { 
     Map.Entry<Character, Integer> e = i.next(); 
     return e.getValue(); 
    } 

    return -1; 
} 

public static void main(String[] args) { 
    System.out.println("firstUniqChar(leetcode) = " + firstUniqChar("leetcode")); 
    System.out.println("firstUniqChar(loveleetcode) = " + firstUniqChar("loveleetcode")); 
    System.out.println("firstUniqChar(aaabbbccc) = " + firstUniqChar("aaabbbccc")); 

} 

Answer 2

単純な二パス順（N）

CharFrequency = array [a..z] of integer 
for c in InputString do 
    inc(CharFrequency[c]) 
i = 0 
while (i < Length(InputString)) and (CharFrequency[InputString[i]] <> 1) do 
    inc(i) 
if (i < Length(InputString)) 
    print(i) 
else 
    print(-1)