Python无需额外模块高效统计单词出现次数的实现方案

我正在解决HackerRank平台的Word Order题目，任务要求如下：

1. 从stdin读取输入，输入示例：

4
bcdef
abcdefg
bcde
bcdef

2. 输出满足以下要求：

• 第一行输出不重复单词的总数
• 第二行按单词第一次出现的顺序输出每个不重复单词的出现次数

输出示例：

3       # 不重复单词总数
2 1 1   # 单词出现次数，'bcdef'出现2次

遇到的问题 #

已编写两个解决方案：第二个方案通过了初始测试，但运行超出时间限制报错；第一个方案可正常运行，但存在不必要的输出排序逻辑，同样会触发超时问题。

注意要求 #

• 第一个方案中不必要的排序逻辑已在第二个方案中修复
• 仅可使用Python标准数据结构、列表/字典推导式实现需求，除import os外不允许导入任何额外模块，需要符合要求的高效实现方案。

import os

def word_order(words):
    # Output no of distinct words
    distinct_words = set(words)
    n_distinct_words = len(distinct_words)
    print(str(n_distinct_words))
    
    # Count occurrences of each word
    occurrences = []
    
    for distinct_word in distinct_words:
        n_word_appearances = 0
        for word in words:
            if word == distinct_word:
                n_word_appearances += 1
        occurrences.append(n_word_appearances)
    occurrences.sort(reverse=True)
    print(*occurrences, sep=' ')
    # for o in occurrences:
    #     print(o, end=' ')
    
def word_order_two(words):
    '''
    Run through all words and only count multiple occurrences, do the maths
    to calculate unique words, etc. Attempt to construct a dictionary to make
    the operation more memory efficient.
    '''
    # Construct a count of word occurrences
    dictionary_words = {word:words.count(word) for word in words}
    
    # Unique words are equivalent to dictionary keys
    unique_words = len(dictionary_words)
    
    # Obtain sorted dictionary values
    # sorted_values = sorted(dictionary_words.values(), reverse=True)
    result_values = " ".join(str(value) for value in dictionary_words.values())
    # Output results
    print(str(unique_words))
    print(result_values)
    return 0

if __name__ == '__main__':
    q = int(input().strip())

    inputs = []
    for q_itr in range(q):
        s = input()
        inputs.append(s)
        
    # word_order(words=inputs)
    word_order_two(words=inputs)

现有方案超时的核心原因是时间复杂度为O(n²)：第一个方案采用双层循环统计次数，第二个方案的字典推导式中每次调用words.count()都会全量遍历单词列表。优化方案仅需一次遍历完成计数，时间复杂度为O(n)，完全满足性能要求，实现代码如下：

import os

def word_order(words):
    count_dict = {}
    for word in words:
        count_dict[word] = count_dict.get(word, 0) + 1
    print(len(count_dict))
    print(' '.join(map(str, count_dict.values())))

if __name__ == '__main__':
    q = int(input().strip())
    inputs = [input() for _ in range(q)]
    word_order(inputs)

若需要用推导式风格实现，可调整为：

import os

def word_order(words):
    count_dict = {}
    [count_dict.__setitem__(word, count_dict.get(word, 0) + 1) for word in words]
    print(len(count_dict))
    print(' '.join(map(str, count_dict.values())))

if __name__ == '__main__':
    q = int(input().strip())
    inputs = [input() for _ in range(q)]
    word_order(inputs)

注：Python3.7及以上版本默认字典保留插入顺序，刚好匹配题目要求的输出顺序与单词第一次出现顺序一致的规则。

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