0

LeetCodeでSort Characters By Frequencyを解決しようとしています。最初に使用した二項演算子は TLE を提供しますが、複合代入演算子を使用すると問題なく動作します。しかし、私はその理由を理解していません。

その背後に何かロジックはありますか？以下に両方のコードを添付しますので、自分で試してみてください。

これにより、TLEが得られます

class Solution {
public:
    string frequencySort(string s) {
        
        unordered_map<char, int> m;
        for(int i = 0; i < s.length(); i++)
            m[s[i]]++;
        
        priority_queue<pair<int, char>> pq; // maxheap based on frequency
        for(auto x = m.begin(); x != m.end(); x++)
            pq.push(make_pair(x->second, x->first));
        
        string ans = "";
        while (!pq.empty())
        {
            for(int i = 0; i < pq.top().first; i++)
                ans = ans + pq.top().second;
            pq.pop();
        }
        
        return ans;
    }
};

これはうまくいきます

class Solution {
public:
    string frequencySort(string s) {
        
        unordered_map<char, int> m;
        for(int i = 0; i < s.length(); i++)
            m[s[i]]++;
        
        priority_queue<pair<int, char>> pq; // maxheap based on frequency
        for(auto x = m.begin(); x != m.end(); x++)
            pq.push(make_pair(x->second, x->first));
        
        string ans = "";
        while (!pq.empty())
        {
            for(int i = 0; i < pq.top().first; i++)
                ans += pq.top().second;
            pq.pop();
        }
        
        return ans;
    }
};
4

1 に答える 1

3

ans = ans + pq.top().second;一時的な文字列を作成し、それを に移動しansます。小さな文字列の最適化が適用されない限り、各操作にはメモリの割り当てと割り当て解除が含まれます。

ans += pq.top().second;は一時的なものを作成せず、以前に予約したメモリansが使い果たされた場合にのみメモリが割り当てられます。これははるかに少ない頻度で発生します。

于 2021-09-28T15:29:01.913 に答える