這是什麼算法

需要找到大O的複雜性對我這個LeetCode problem的解決方案的大哦複雜。這是什麼算法

當檢測到重複字符時，由於隊列中的重複刪除操作，我無法估計複雜度，如果沒有它，則由於經過字符串的單個for循環，應該爲O（n）。

發佈問題的要點和我供你參考的解決方案：

給定一個字符串，找到最長的字符串的長度而不重複字符。

實例：

鑑於「abcabcbb」，答案是「ABC」，其長度爲3

鑑於「BBBBB」，答案爲「b」，具有1的長度。

鑑於「pwwkew」，答案是「wke」，長度爲3.請注意，答案必須是子字符串，「pwke」是子序列，而不是子字符串。

我的解決辦法：

import java.util.Hashtable; 
public class Solution { 
    public int lengthOfLongestSubstring(String s) { 
     Queue<Character> q = new LinkedList<Character>(); 
     Hashtable<Character, Boolean> chars = new Hashtable<Character, Boolean>(); 
     int maxLen = 0; 
     for (int i = 0; i < s.length(); i++) 
     { 
      char ch = s.charAt(i); 
      if (!chars.containsKey(ch)) 
      { 
       q.add(ch); 
       chars.put(ch,true); 
      } 
      else 
      { 
       int len = q.size(); 
       System.out.println(len); 
       while(q.peek()!=ch) 
       { 
        chars.remove(q.remove()); 
       } 
       q.remove(); 
       q.add(ch); 
       if (len > maxLen) 
       maxLen = len; 
      } 
     } 
     if (q.size() > maxLen) 
      return q.size(); 
     return maxLen; 
    } 
}

來源

2017-02-07 Flame of udun

您的解決方案將是爲O（n）。無論在for循環中是什麼並不重要，而是循環運行的次數是多少。這是因爲循環的內部部分將是一些任意數量的操作，它們將會是一個常量。由於在大O上，我們不關心什麼常量，更重要的是循環的運行次數的數量，這將是N.

也許一些數學可以幫助演示：

說N = 5和你不知道循環會執行多少操作，但是您知道它將運行5次。首先假設它只進行一次操作，那麼當然操作次數是5，即1 * N。然後假設循環執行100次操作，那麼操作次數是500，即100 * N。在這兩種情況下，大O都是O（n）。然後你可以假設對於一些任意數量的循環操作，你仍然會得到O（n）。我不知道數學是多麼有效，但總的想法是有道理的。

來源

2017-02-07 16:06:35 Developer

但也有一個while循環在for循環可能被重複調用。這不會有什麼區別嗎？ –

糟糕我在看網站的解決方案，而不是你的，我沒有看到while循環。在這種情況下，你能弄清楚while循環的最壞情況是什麼？有沒有一個例子，你可以讓每個if/else都去else子句，然後做n次while循環？ – Developer

這是什麼算法

回答

相關問題