题解 | #重排字符串#

class Solution {
  public:

    string rearrangestring(string str) {
        // write code here
        // Step 1:统计所有出现字符的出现次数
        unordered_map<char, int> char_count;
        for (char c : str) {
            char_count[c]++;
        }

        // Step 2：大堆顶的优先级队列比较的 lambda表达式 
        auto compare = [](pair<int, char>& a, pair<int, char>& b) {
            return a.first < b.first;
        };
	  //priority_queue 是一个模板类，用于实现优先队列，其中的元素按照一定的优先级顺序进行排列，
	  //默认情况下是大顶堆（即最大元素优先）。
	  //模板参数中：
	  //pair<int, char> 表示队列中存储的元素类型，这里是频次（int）和字符（char）的组合。
	  //vector<pair<int, char>> 表示用于存储元素的底层容器类型，这里选择了 vector.
	  //decltype(compare) 表示比较函数的类型，由于 compare 是一个 lambda 表达式，
	  //我们使用 decltype 来推导出其类型。
        priority_queue<pair<int, char>, vector<pair<int, char>>, decltype(compare)>
                		max_heap(compare);
	  //将数据的压入堆中
        for (auto& entry : char_count) {
            max_heap.push({entry.second, entry.first});
        }

        // Step 3: 重建字符串
        string result;
	    //临时对象，表示前一个
        pair<int, char> prev = {-1, '#'};
	  
        while (!max_heap.empty()) {
		  //当前位置
            pair<int, char> current = max_heap.top();
            max_heap.pop();

            // 如果前一个对象剩余个数>0,将前一个对象压入堆中
            if (prev.first > 0) {
                max_heap.push(prev);
            }

            // 将当前对像的值写入result中
            result += current.second;

            //当前对象出现次数减1
            current.first--;
		    //将当前对象赋值给前一个对象
            prev = current;
        }

        //检查结果字符串长度是否相等，如果不相等，则表示无法返回
        if (result.length() != str.length()) {
            return "";
        }

        return result;
    }
};