将字典的长度修改为确定的值并保留具有最高值的键

Question

大家好，我正在编写这个脚本，我需要更新一个字典words，其中最常用的单词仅限于limit.from typing import List, Dict, TextIO, Tupledef most_frequent(words: Dict[str, int], limit: int) -> None:new_dict = {}new_list = []#I decided to create a list for easier sortfor w in words:    new_list.append((keys, words.get(w)))    new_list.sort(key=sorting, reverse=True)    #key=sorting: used to sort by the value of the key from big to small for n_w in new_list:    if len(new_dict) < limit:        new_dict[n_w[0]] = n_w[1]#this part add the words to a new dictionary up to the value of limitwords = new_dictprint(words)#print just to check my result, I know it's supposed to return None这是问题所在，我需要实现以下测试用例，其中：len(words) <= limit，如果添加了最常用的单词并导致结果，len(words) > limit则不添加任何单词；如果最后一个单词不是唯一的并且与下一个单词具有相同的值，则也不会添加任何一个。>>> most_frequent({'cat': 3, 'dog': 3, 'pig': 3, 'bee': 3, 'rat': 1}, 4){'cat': 3, 'dog': 3, 'pig': 3, 'bee': 3}#This one passes>>> most_frequent({'cat': 3, 'dog': 3, 'pig': 3, 'bee': 2, 'rat': 2}, 4){'cat': 3, 'dog': 3, 'pig': 3}#what I get {'cat': 3, 'dog': 3, 'pig': 3, 'bee': 2},  'bee' doesn't get added because is tied with 'rat'>>> most_frequent({'cat': 3, 'dog': 3, 'pig': 3, 'bee': 3, 'rat': 1}, 3)  {}#what I get {'cat': 3, 'dog': 3, 'pig': 3}, none of them are added because there are 4 with high frequency but if they get added words > limit and it can't be我觉得我现在使用的方法对于我需要的东西效率不高，而且我陷入了最后两种情况。我不允许使用模块，我应该使用什么方法？或者至少我可以在这里改进什么以获得我需要的东西？

Answer 1

我会做这样的事情：

def most_frequent(words, limit):

    frequencies = words.items()

    inverse = {}

    for word, frequency in frequencies:

        inverse.setdefault(frequency, []).append(word)

    result = {}

    remaining = limit

    for frequency in sorted(inverse.keys(), reverse=True):

        if len(inverse[frequency]) <= remaining:

            result.update({word: frequency for word in inverse[frequency]})

            remaining -= len(inverse[frequency])

        else:

            break

    return result

print(most_frequent({'cat': 3, 'dog': 3, 'pig': 3, 'bee': 3, 'rat': 1}, 4))

print(most_frequent({'cat': 3, 'dog': 3, 'pig': 3, 'bee': 2, 'rat': 2}, 4))

print(most_frequent({'cat': 3, 'dog': 3, 'pig': 3, 'bee': 3, 'rat': 1}, 3))

输出

{'bee': 3, 'dog': 3, 'pig': 3, 'cat': 3}

{'dog': 3, 'pig': 3, 'cat': 3}

{}

这个想法是创建一个倒排字典（inverse），其中键是频率，值是具有该频率的单词列表，然后您可以按非升序迭代频率，并将单词列表添加到最终结果中如果剩余预算允许。