算法，在O(n*log(k))中找到k个最大数

Question

想知道，是否给出了一个任意长度的数组的未排序列表n>=k你的想法是什么，找到O(n*log(k((时间内的k最大数。因此，例如，包含数字1到9的数组的k=2最大数为8。

如果你知道在这种复杂的时间里如何做到这一点，我正试图用python来编码：(

Answer 1

我的答案不是特定于python的，但是您应该能够在python中实现所使用的概念，或者找到已经实现它们的库。

基本思想是迭代列表并存储当前最大值、第二大值，k——独立数据结构中的最大数。由于您将对数组中的所有n个条目进行迭代，因此其复杂性在O(n * insertion_step_complexity)
如上所述，插入步骤不需要超过O(log(k))的复杂性即可实现这一点。您可以使用复杂性为O(log(m))的AVL-Tree来插入和删除项目，其中m是存储在avl树中的项目数。

一个算法看起来像这样：

def find_k_greatest_number(k, array):
avl_tree = initialize AVL tree here
avl_items = 0
for number in array:
if (number > avl_tree.smallest_number()):
if (avl_itmes >= k):
avl_tree.delete_smallest_number()
else:
avl_items++
avl_tree.insert(number)
return avl_tree.smallest_number()

在排序树中找到最小的数字取决于它的高度。由于AVL树不能超过log(k)的高度，因此找到最小数的复杂度是O(log(k))。