优化Python多字符串索引高频字符提取函数的性能

原代码的性能瓶颈 #

原代码的核心问题在于重复计算和冗余操作：

• 每次调用value.count(x)都会遍历整个字符列表，对于100k级别的数据，这会导致**O(n²)**的时间复杂度，重复计算量巨大。
• sorted(value)会生成完整的字符排序列表，完全是不必要的内存和时间开销。

优化思路 #

核心是提前一次性统计每个索引的字符频率，再基于频率直接选择符合要求的字符：

1. 用双层字典统计每个索引下各字符的出现次数，遍历所有字符仅一次。
2. 对每个索引的频率字典，通过max函数的自定义key，直接选出「频率最高、同频率下字典序最小」的字符，无需重复计数或排序。

优化后的代码 #

def f(words: list) -> str:
    freq = {}
    max_len = 0
    for word in words:
        # 跟踪最长字符串长度，确保结果长度符合要求
        current_len = len(word)
        if current_len > max_len:
            max_len = current_len
        # 统计每个索引的字符频率
        for idx, char in enumerate(word):
            if idx not in freq:
                freq[idx] = {}
            freq[idx][char] = freq[idx].get(char, 0) + 1
    
    result = []
    for idx in range(max_len):
        char_counts = freq.get(idx, {})
        # 按「负频率（降序）、字符（升序）」排序，直接取最优字符
        best_char = max(char_counts.items(), key=lambda item: (-item[1], item[0]))[0]
        result.append(best_char)
    
    return ''.join(result)

优化点说明 #

1. O(N)时间复杂度的频率统计：遍历所有字符仅一次完成计数，无重复计算，适合大数据量场景。
2. 高效的最优字符选择：通过(-item[1], item[0])作为排序key，优先按频率降序，同频率时按字符字典序升序，一次max调用即可得到结果，避免了原代码的冗余排序和计数。
3. 可靠的长度控制：主动跟踪最长字符串长度，显式遍历所有索引，确保结果长度严格符合要求，同时避免依赖字典插入顺序的潜在问题。

内容的提问来源于stack exchange，提问作者user20480001