排序字符频率
题目描述
给定一个字符串 s，请将字符串中的字符按照出现频率降序排列。如果有多个字符出现频率相同，则按字符的原始顺序排列（注意：某些编程语言中可能无法直接保持非稳定排序的原始顺序，需特殊处理）。例如，输入 "tree" 应返回 "eert" 或 "eetr"（若要求稳定排序则需额外处理）。

解题步骤

1. 统计字符频率

   • 遍历字符串，使用哈希表（如 Python 的 defaultdict 或 Counter）记录每个字符出现的次数。
   • 示例：s = "tree" → 统计结果：{'t': 1, 'r': 1, 'e': 2}。

2. 按频率分组

   • 创建另一个哈希表（或列表），以频率为键，对应字符列表为值。注意：相同频率的字符需按首次出现的顺序存储（若需稳定排序）。
   • 示例：频率分组：{2: ['e'], 1: ['t', 'r']}（顺序与原字符串中一致）。

3. 按频率降序处理

   • 确定最大频率值（如 max_freq = 2），从最高频率到最低频率遍历。
   • 对于每个频率，按顺序取出字符，重复该字符频率次数的字符并拼接。
   • 示例：
     • 频率 2：'e' → "ee"
     • 频率 1：'t', 'r' → "t" + "r" = "tr"
     • 结果："ee" + "tr" = "eetr"

4. 处理稳定性（关键点）

   • 若语言内置排序不稳定（如 Python 的 sorted 默认稳定，但需显式指定），需在分组时保留原始顺序。
   • 替代方法：使用桶排序，以频率为桶索引，桶内保持字符顺序。

示例代码（Python）

from collections import Counter

def frequencySort(s: str) -> str:
    # 统计频率
    freq_map = Counter(s)
    
    # 分组：按频率降序，同频率按原顺序
    max_freq = max(freq_map.values())
    buckets = [[] for _ in range(max_freq + 1)]
    for char in s:  # 按原顺序遍历以保持稳定性
        f = freq_map[char]
        if char not in buckets[f]:
            buckets[f].append(char)
    
    # 从高频率到低频率拼接结果
    result = []
    for i in range(max_freq, 0, -1):
        for char in buckets[i]:
            result.append(char * i)
    return ''.join(result)

复杂度分析

• 时间复杂度：O(n)（遍历统计 + 桶排序处理）。
• 空间复杂度：O(n)（哈希表和桶存储）。

关键思路
通过桶排序保持相同频率字符的原始顺序，避免使用不稳定的通用排序算法直接对字符排序。