Update 0451. 根据字符出现频率排序.md

itcharge · itcharge · commit 34f3b8d77b35 · 2022-09-07T18:06:04.000+08:00
diff --git a/Solutions/0451. 根据字符出现频率排序.md b/Solutions/0451. 根据字符出现频率排序.md
@@ -5,65 +5,45 @@
 
 ## 题目大意
 
-给定一个字符串 `s`。
+**描述**：给定一个字符串 `s`。
 
-要求：将字符串 `s` 里的字符按照出现的频率降序排列。
+**要求**：将字符串 `s` 里的字符按照出现的频率降序排列。如果有多个答案，返回其中任何一个。
 
-## 解题思路
+**说明**：
+
+- $1 \le s.length \le 5 * 10^5$。
+- `s` 由大小写英文字母和数字组成。
+
+**示例**：
+
+```Python
+输入: s = "tree"
+输出: "eert"
+解释: 'e'出现两次，'r'和't'都只出现一次。
+因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
+
+
+输入: s = "cccaaa"
+输出: "cccaaa"
+解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
+注意"cacaca"是不正确的，因为相同的字母必须放在一起。
+```
 
-使用哈希表统计字符频率。然后使用 `set` 集合对字符串去重并转换为 `list` 数组。
+## 解题思路
 
-然后按照字符频数对新的字符串数组进行排序。将堆中频数最高的元素依次加入答案数组中，并不断调整剩余元素构成的大顶堆。
+### 思路 1：优先队列
 
-最后输出答案数组。
+1. 使用哈希表 `s_dict` 统计字符频率。
+2. 然后遍历哈希表 `s_dict`，将字符以及字符频数存入优先队列中。
+3. 将优先队列中频数最高的元素依次加入答案数组中。
+4. 最后拼接答案数组为字符串，将其返回。
 
-## 代码
+### 思路 1：代码
 
 ```Python
-class Solution:
-    # 调整为大顶堆
-    def heapify(self, nums, nums_dict, index, end):
-        left = index * 2 + 1
-        right = left + 1
-        while left <= end:
-            # 当前节点为非叶子节点
-            max_index = index
-            if nums_dict[nums[left]] > nums_dict[nums[max_index]]:
-                max_index = left
-            if nums_dict[nums[left]] == nums_dict[nums[max_index]]:
-                if nums[left] > nums[max_index]:
-                    max_index = left
-            if right <= end and nums_dict[nums[right]] > nums_dict[nums[max_index]]:
-                max_index = right
-            if right <= end and nums_dict[nums[right]] == nums_dict[nums[max_index]]:
-                if nums[right] > nums[max_index]:
-                    max_index = right
-            if index == max_index:
-                # 如果不用交换，则说明已经交换结束
-                break
-            nums[index], nums[max_index] = nums[max_index], nums[index]
-            # 继续调整子树
-            index = max_index
-            left = index * 2 + 1
-            right = left + 1
-
-    # 初始化大顶堆
-    def buildMaxHeap(self, nums, nums_dict):
-        size = len(nums)
-        # (size-2) // 2 是最后一个非叶节点，叶节点不用调整
-        for i in range((size - 2) // 2, -1, -1):
-            self.heapify(nums, nums_dict, i, size - 1)
-        return nums
-
-    # 堆排序方法（本题未用到）
-    def maxHeapSort(self, nums, nums_dict):
-        self.buildMaxHeap(nums)
-        size = len(nums)
-        for i in range(size):
-            nums[0], nums[size - i - 1] = nums[size - i - 1], nums[0]
-            self.heapify(nums, nums_dict, 0, size - i - 2)
-        return nums
+import heapq
 
+class Solution:
     def frequencySort(self, s: str) -> str:
         # 统计元素频数
         s_dict = dict()
@@ -72,19 +52,23 @@ class Solution:
                 s_dict[ch] += 1
             else:
                 s_dict[ch] = 1
-
-        # 使用 set 方法去重，得到新数组
-        new_s = list(s)
-        size = len(new_s)
-        # 初始化大顶堆
-        self.buildMaxHeap(new_s, s_dict)
-        res = list()
-        for i in range(size):
-            # 堆顶元素为当前堆中频数最高的元素，将其加入答案中
-            res.append(new_s[0])
-            # 交换堆顶和末尾元素，继续调整大顶堆
-            new_s[0], new_s[size - i - 1] = new_s[size - i - 1], new_s[0]
-            self.heapify(new_s, s_dict, 0, size - i - 2)
+        
+        priority_queue = []
+        for ch in s_dict:
+            heapq.heappush(priority_queue, (-s_dict[ch], ch))
+        
+        res = []
+        while priority_queue:
+            ch = heapq.heappop(priority_queue)[-1]
+            times = s_dict[ch]
+            while times:
+                res.append(ch)
+                times -= 1
         return ''.join(res)
 ```
 
+### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n  + k \times log_2k)$。其中 $n$ 为字符串 $s$ 的长度，$k$ 是字符串中不同字符的个数。
+- **空间复杂度**：$O(n + k)$。
+
