java - 删除多余空格函数的时间复杂度

Question

我编写了一个函数，可以在不使用替换函数的情况下用单个空格删除连续空格。但是，我对该函数的时间复杂度/是否有更好的方法来实现它感到困惑。

static String removeSpaces(String s){
    StringBuffer sb = new StringBuffer();
    if (s == null){
        return "";
    }
    if (s.length() == 0){
        return "";
    }
    for (int i=0;i<s.length();i++){
        if (s.charAt(i) == ' '){
            sb.append(" ");
            if (i < s.length() - 1){
                while (s.charAt(i) == ' '){
                    i++;
                }
            }
        }
        sb.append(s.charAt(i));

    }
    return sb.toString();
}

Answer 1

首先，您应该注意正确性。最里面的循环， while (s.charAt(i) == ' '){ i++; } 不会检查边界，一旦代码进入就会中断，如果 String 末尾有多个空格，就会发生这种情况。

除此之外，时间复杂度是O(n)并且你无法提高复杂度。这并不意味着没有什么是你无法改进的。复杂性仅告诉您，解决方案如何扩展大量数字，即本例中较大的String。

考虑:

static String removeSpaces(String s) {
    // check preconditions for fast exit before creating new objects
    if (s == null || s.isEmpty()) {
        return "";
    }
    // use StringBuilder for pure local operations to avoid synchronization costs
    StringBuilder sb = new StringBuilder();
    for (int i=0;i<s.length();i++) {
        sb.append(s.charAt(i)); // the code is always the same for all characters
        // now skip runs of spaces
        if(s.charAt(i)==' ') {
            while(i<s.length()-1 && s.charAt(i+1) == ' ') {
                i++;
            }
        }
    }
    return sb.toString();
}

首先，这段代码更简单，这可能比执行速度的微小改进更重要，但是，大多数环境往往会更快地执行较小的循环。

但是时间复杂度仍然是O(n)...

<小时/>

但请注意，您可以简化整个操作return s.replaceAll("+", "");...