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

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

  • 标签:哈希表、字符串、桶排序、计数、排序、堆(优先队列)
  • 难度:中等

题目大意 #

描述:给定一个字符串 s

要求:将字符串 s 里的字符按照出现的频率降序排列。如果有多个答案,返回其中任何一个。

说明

  • $1 \le s.length \le 5 * 10^5$。
  • s 由大小写英文字母和数字组成。

示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
输入: s = "tree"
输出: "eert"
解释: 'e'出现两次'r''t'都只出现一次
因此'e'必须出现在'r''t'之前此外"eetr"也是一个有效的答案


输入: s = "cccaaa"
输出: "cccaaa"
解释: 'c''a'都出现三次此外"aaaccc"也是有效的答案
注意"cacaca"是不正确的因为相同的字母必须放在一起

解题思路 #

思路 1:优先队列 #

  1. 使用哈希表 s_dict 统计字符频率。
  2. 然后遍历哈希表 s_dict,将字符以及字符频数存入优先队列中。
  3. 将优先队列中频数最高的元素依次加入答案数组中。
  4. 最后拼接答案数组为字符串,将其返回。

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import heapq

class Solution:
    def frequencySort(self, s: str) -> str:
        # 统计元素频数
        s_dict = dict()
        for ch in s:
            if ch in s_dict:
                s_dict[ch] += 1
            else:
                s_dict[ch] = 1
        
        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)$。
本站总访问量  次  |  您是本站第  位访问者