toCharArray() 是否消耗 Big O 中的空间

Question

在计算算法的空间复杂度时，我们被告知找出额外空间的最简单方法是创建数据结构，如 Set、Map、Stack 等。

以下面的代码为例，它尊重字符串（在Java中）

private String reverse(String string){

    if (string == null || string.length() == 0) return string;

    char[] strArray = string.toCharArray(); // Does this consume space?

    int first = 0, last = strArray.length - 1;

    while (first < last){
        char temp = strArray[first];
        strArray[first++] = strArray[last];
        strArray[last--] = temp;
    }


    return String.valueOf(strArray);
}

str转字符数组会占用空间吗

Answer 1

根据Stringjavadoc，toCharArray创建“一个新分配的字符数组，其长度是该字符串的长度，其内容被初始化为包含该字符串表示的字符序列”。因此，调用的toCharArray空间复杂度为 O(n)。