Java StringBuilder 高效删除最后一次出现的字符

Question

从 StringBuilder 中删除最后一次出现的 char 的最有效方法是什么？

我目前的解决方案是O(N)，但我觉得这个问题可以在常数时间内解决。

public StringBuilder deleteLastOccurance(StringBuilder builder, char c) {        
    int lastIndex = builder.lastIndexOf(String.valueOf(c));
    if (lastIndex != -1) {
        builder.deleteCharAt(lastIndex); // O(N)
    }
    return builder;
}

Answer 1

无论如何，最终都会花费 O(n) 时间。如果不一直检查到最后，没有其他方法可以确定最后一个字符。

即使是内部 java API 方法也将具有相同的底层实现。