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

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