爲什麼這個算法很慢？

Question

給定一個字符串，找到它中的第一個非重複字符並返回它的索引。如果它不存在，則返回-1。

S = 「本文給出了」 返回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

不要做一個內部循環。交易時間空間並隨時跟蹤哪些字符是唯一的或不是當您穿越字符串一次。

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）僞代碼算法（對於只包含一個字符範圍「a」到「z」的字符串）可能是這樣的

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)