0

我正在尝试解决LeetCode 上按频率排序字符的问题。第一个使用的二元运算符给了我一个 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 回答