前K个常用词卡在一个部分

Question

这是指leetcode问题：https://leetcode.com/problems/top-k-frequent-words/ 这是我的密码：

import heapq

class Solution:
# def topKFrequent(self, words: List[str], k: int) -> List[str]:
def topKFrequent(self, words, k):
    results = []
    wordTable = {}
    for word in words:
        if (wordTable.get(word) is None):
            wordTable[word] = 1
            continue
        wordTable[word] = (wordTable.get(word)) + 1

    heap = []
    # print(wordTable)
    heapSize = 0

    for word in wordTable.keys():
        node = [wordTable[word], word]
        if(heapSize<k):
            heapq.heappush(heap,node)
            heapSize += 1
            continue
        if(heapSize>=k):
            if (heap[0][0]< node[0]):
                heapq.heappushpop(heap,node)
                heapSize -= 1
                continue
            if heap[0][0] == node[0] and heap[0][1]>node[1]:
                heapq.heappop(heap)
                heapq.heappush(heap,node)
                heapSize -= 1
                continue

    # heap.sort(key = lambda x: x.freq, reverse=True);
    print(heap)

    for i in reversed(range(k)):
        results.append(heap[i][1])
    return results

如果所有单词的频率都不同，那么代码就可以工作，因为它使用一个最小堆。但是，如果它们的频率相同，则不起作用，因为它们的顺序相反，因此字母顺序较大的单词排在不被接受的第一位（例如，如果我有4个频率相同的单词，假设它们是a、b、c、d：我的结果将是d、c、b、a，这是不可接受的） 我不知道如何解释这个案例，我在这个问题上被困了3个小时。 有人能帮忙吗

Answer 1

这一行应该对你有帮助

from collections import Counter

topk = lambda words, k: [t[0] for t in Counter(list(sorted(words))).most_common(k)]

print(topk(["i", "love", "leetcode", "i", "love", "coding"], k=2))
print(topk(["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k=4))

# Output
['i', 'love']
['the', 'is', 'sunny', 'day']

1. 第一步是使用 list(sorted(words))
2. 计数器将list转换为频率。它是内置的 heapq
3. most_common(k)顾名思义，它给了你最大的帮助 常用词。但请注意，我们已经对它们进行了排序 按词典编纂
4. 最后一个外部for循环只需使用第一个 most_common(k)函数返回的元组的值

Answer 2

使用functools.cmp_to_key

from functools import cmp_to_key

def cmp(a, b):
    if a[0] == b[0]:
         return -1 if a[1] < b[1] else 1
    return -1 if a[0] > b[0] else 1
return sorted(heap, key=cmp_to_key(cmp))