向字符串添加空格算法调优

问题链接是

我写的代码

class Solution {
    public String addSpaces(String s, int[] spaces) {
        StringBuilder stringBuilder = new StringBuilder(s);
        int c = 0;
        for (int v : spaces) {
            stringBuilder.insert(v + c++, ' ');
        }
        return stringBuilder.toString();
    }
}

img

但是不知道为什么性能很差，不是说频繁的字符串拼接用StringBuilder性能好吗？

我现在的方案怎么优化呢

StringBuilder 的 insert 复杂度是 n，所以你每次插入都要遍历一次 整个 StringBuilder 字符串

img

img

性能并不如你想象的好。建议改用 StringBuilder 的 append 方法

public String addSpaces(String s, int[] spaces) {
    StringBuilder stringBuilder = new StringBuilder();
    int p1 = 0, p2 = 0, len = s.length(), n = spaces.length;
    while (p1 < len) {
        if (p2 < n && p1 == spaces[p2]) {
            stringBuilder.append(' ');
            p2++;
        }
        stringBuilder.append(s.charAt(p1++));
    }
    while (p2++ < n) {
        stringBuilder.append(' ');
    }
    return stringBuilder.toString();
}

我提交了下测试结果为

img

它只是相对StringBuffer性能更好，但还是很耗时的

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        string ans;
        ans.reserve(s.size()+spaces.size());//预开辟空间
        int i = 0, j = 0, n = spaces.size();
        while(i < n)
        {
            while(j < spaces[i])
                ans.push_back(s[j++]);
            ans.push_back(' ');
            i++;
        }
        while(j < s.size())
            ans.push_back(s[j++]);
        return ans;
    }
};

可以参考这个

如有帮助，采纳支持一下，谢谢。

刷了一波题

 char[] chars = s.toCharArray();
        char[] result = new char[s.length() + spaces.length];
        int sp = 0,index = 0;
        for(int i=0;i<chars.length;i++){
            if(sp < spaces.length && spaces[sp] == i){
                result[index++] = ' ';
                sp++;
            }
            result[index++] = chars[i];
        }
        return new String(result);

img