在字符串中查找重复 - 订单复杂度

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; 
}