“前k个最频繁元素”的最差运行时复杂度分析

问题描述:

给定一个非空的单词列表,返回k最频繁的元素。

你的答案应该按频率从高到低排序。如果 两个词有相同的频率,然后是较低频率的词 按字母顺序排列。

例如:例1:输入:[“i”,“love”,“stackoverflow”,“i”,“love”, “编码”],k=2输出:【I”,“爱”】解释:“I”和“爱”是 两个最常见的词。注意“我”在“爱”之前是因为 较低的字母顺序。

使用频率桶的python解决方案:

def topKFrequent(words, k):       
    wordCount = collections.Counter(words)
    freq = [[] for i in range(len(words) + 1)]
    res = []
    for word, count in wordCount.items():
        freq[count].append(word)
    for i in range(len(freq) - 1, 0, -1):
        if k == 0:
            break
        elif k >= len(freq[i]):
            res.extend(sorted(freq[i]))
            k -= len(freq[i])
        else:
            res.extend(sorted(freq[i])[:k])
            break
    return res

现在,我的论点是,上面的运行在o(nlogn)中,忽略了计数器初始化和freq初始化,每个都是o(n),在最坏的情况下,最后一个循环将有一个包含所有单词的bucket(每个单词恰好出现一次),所以我们最终只对该bucket进行排序。,即nlog(n)。

以上是正确的直观分析吗?