算法题之根据字符出现频率排序

发表于 | 分类于 | 阅读次数：
本文字数： 1.1k | 阅读时长 ≈ 1 分钟
给定一个字符串，请将字符串里的字符按照出现的频率降序排列
leetcode 451. Sort Characters By Frequency

算法1

题目描述

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

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

示例 3:

输入:
"Aabb"

输出:
"bbAa"

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

解决方案(Python)

  1. 生成字符与字符出现次数的字典（key为字符本符，value为字符出现次数）
  2. 以s_dict的value进行排序（降序），生成在一个列表中
  3. 合成为最终字符串返回
def str_sort(s):
    """
    给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
    :param str s: 输入字符串
    :return: 根据字符出现数量排序（降序）后的字符串
    :rtype: str
    """
    # 1.生成字符与字符出现次数的字典（key为字符本符，value为字符出现次数）
    s_dict = {}
    for c in s:
        s_dict = s_dict.get(c, 0) + 1
        
    # 2.以s_dict的value进行排序（降序），生成在一个列表中
    sorted_list = sorted(s_dict.items(), key=lambda x: x[1], reverse=True)  # return list
    
    # 3.合成为最终字符串返回
    return ''.join([c * n for c, n in sorted_list])
---------------- The End ----------------
0%