451在leetcode中提示超出内存限制

Question

typedef pair<char, int> PAIR;

struct CmpByValue {
    bool operator()(const PAIR& lhs, const PAIR& rhs) {
        return lhs.second > rhs.second;
    }
};

string frequencySort(string s) {
    map<char,int> record;
    for(int i=0;i<s.size();i++)
        record[s[i]]++;

    vector<PAIR> name_count_vec(record.begin(),record.end());
    sort(name_count_vec.begin(),name_count_vec.end(),CmpByValue());

    string ret="";
    for(vector<PAIR>::iterator it=name_count_vec.begin();it!=name_count_vec.end();it++){
        for(int i=0;i<it->second;i++){
            ret=ret+it->first;
        }
    }
    return ret;
}

老师帮我看下，哪里的问题？

Answer 1

liuyubobobo 2018-08-30 10:03:00

21行每次都取出了一个ret，加上了一个字符，生成了一一个新的字符串，赋给了ret。这个过程不是在ret后面直接添加一个字符，需要申请一个和整个字符串一样大的空间，再赋值会去。

在C++中，改写成如下即可：

ret += it->first;

（+=直接在左操作符引用后面添加有操作符的内容；而+将左右操作符的内容拼接后以新的字符串返回）

在Java中，则一定要使用StringBuilder：）

加油！：）

• 提问者 向往那片天空 #1

  非常感谢！