python - 如何从这个字典列表中找到具有玩家 ID 的 5 个最大分数？

Question

我有一个类似字典的列表。

players_score = [{'playerID': 'bondsba01', 'score': 771.0309445542441}, 
{'playerID': 'brookhu01', 'score': 334.40601958915977}, 
{'playerID': 'jamesbo01', 'score': 885.9822344322345}, 
{'playerID': 'hassero01', 'score': 593.022015503876}, 
{'playerID': 'addybo01', 'score': 785.2226861630111}, 
{'playerID': 'cedence01', 'score': 75.7351748570627}, 
{'playerID': 'eckerde01', 'score': 787.7921476129764}, 
{'playerID': 'wockejo01', 'score': 674.6701980001981}]

我如何使用 python 从这里找到 5 个最大的分数和玩家 ID。谢谢

Answer 1

一种方法是对第一个进行排序并选择在 O(n * log n) 中运行的第一个 k=5 元素:

sorted_list = sorted(players_score, key=lambda x: x['score'], reverse=True)
sorted_list[:5]

#[{'playerID': 'jamesbo01', 'score': 885.9822344322345}, 
#{'playerID': 'eckerde01', 'score': 787.7921476129764}, 
#{'playerID': 'addybo01', 'score': 785.2226861630111}, 
#{'playerID': 'bondsba01', 'score': 771.0309445542441}, 
#{'playerID': 'wockejo01', 'score': 674.6701980001981}]

但是运行这个任务更有效的方法是使用Min Heap，它运行在 O((n-k)*logk):

def FirstKelements(arr, size, k):

    minHeap = []
    for i in range(k):
        minHeap.append(arr[i])

    for i in range(k, size):
        minHeap.sort(key=lambda x: x['score'])

        if (minHeap[0]['score'] > arr[i]['score']):
            continue

        else:
            minHeap.pop(0)
            minHeap.append(arr[i])

    for i in minHeap:
        print(i, end="\n")

FirstKelements(players_score, len(players_score), 5)

#{'playerID': 'bondsba01', 'score': 771.0309445542441} 
# {'playerID': 'addybo01', 'score': 785.2226861630111} 
# {'playerID': 'eckerde01', 'score': 787.7921476129764} 
# {'playerID': 'jamesbo01', 'score': 885.9822344322345} 
# {'playerID': 'wockejo01', 'score': 674.6701980001981}