爲什麼這個算法很慢？

給定一個字符串，找到它中的第一個非重複字符並返回它的索引。如果它不存在，則返回-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; 
    }

來源

2016-11-15 user697911

我認爲這個問題更適合http://codereview.stackexchange.com/ – maffo

一個簡單的O（n）存在...第一遍，計算字符串的每個字母，第二遍找到計數爲1的第一個字母... –

然後你需要一個LinkedHashMap來記錄計數？ – user697911

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

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

}

來源

2016-11-15 20:56:06

簡單的兩通級（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)

來源

2016-11-15 21:04:30 Penguino

爲什麼這個算法很慢？

回答

相關問題