在字符串中查找重複 - 訂單複雜度

Question

有人可以驗證此代碼的訂單複雜度是否爲n（logn）？如果不是，你能解釋你的答案嗎？我真的很感激幫助

public static boolean isDuplicate(String s){ 
     char[] sArray = s.toCharArray(); 
     for(int i=0;i<sArray.length/2;i++){ 
      for(int j=sArray.length/2+1;j<sArray.length;j++){ 
       if(sArray[i] == sArray[j]) 
        return true; 
      } 
     } 
     return false; 
    } 

Answer 1

不，它不是，它是爲O（n^2），因爲你迭代在外環整個數組，併爲i每一個值，你也遍歷內部循環中的整個數組。將數組分成兩部分的事實不會改變訂單的複雜性。

如果你想找到一個Ø重複（N *的log（n））的算法，可以對數組進行排序，並重複檢查在鄰近的地方，這樣的：

public static boolean isDuplicate(String s){ 
    char[] sArray = s.toCharArray(); 
    Arrays.sort(sArray); // O(n*log(n)) 
    for (int i=0; i<sArray.length-1; i++) // O(n) 
     if (sArray[i]==sArray[i+1]) 
      return true; 
    return false; 
} 

更妙，您可以使用HashSet，並在O（n）中找到重複項：

public static boolean isDuplicate(String s){ 
    HashSet<Character> alreadySeenChars = new HashSet<Character>(); 
    char[] sArray = s.toCharArray(); 
    for (int i=0; i<sArray.length; i++) { // O(n) 
     if (alreadySeenChars.contains(sArray[i])) // O(1) 
      return true; 
     alreadySeenChars.add(sArray[i]); // O(1) 
    } 
    return false; 
}