<p>一种方法是对第一个元素进行排序,并选择在<code>O(n * log n)</code>中运行的第一个<code>k=5</code>元素:</p>
<pre class="lang-py prettyprint-override"><code>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}]
</code></pre>
<p>但运行此任务更有效的方法是使用在<code> O((n-k)*logk)</code>中运行的最小堆:</p>
<pre class="lang-py prettyprint-override"><code>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}
</code></pre>