java - 在字符串中查找重复项 - 顺序复杂性

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，您也在内部循环中迭代整个数组。将数组一分为二这一事实不会改变订单的复杂性。

如果要使用 O(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;
}

更好的是，您可以使用 a 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;
}