python - 获取列表中 X 个最大数字的索引

Question

请不要使用 len() 或 range() 之外的内置函数。我正在为期末考试学习。

这是我的意思的一个例子。

def find_numbers(x, lst):


lst = [3, 8, 1, 2, 0, 4, 8, 5]

find_numbers(3, lst) # this should return -> (1, 6, 7)

我没有完全尝试这个......无法找出最好的方法:

def find_K_highest(lst, k):
 newlst = [0] * k
 maxvalue = lst[0]


 for i in range(len(lst)):
    if lst[i] > maxvalue:
        maxvalue = lst[i]
        newlst[0] = i

Answer 1

从列表中取出前 3 (x) 个数字。最大值的最小值是这些。在您的例子中:3、8、1。它们的索引是 (0、1、2)。构建它们对 ((3,0), (8,1), (1,2))。

现在按最大值的大小对它们进行排序:((8,1), (3,0), (1,2))。

有了这个初始列表，你可以递归地遍历列表的其余部分。将最小值 (1, _) 与列表中的下一个元素 (2, 3) 进行比较。如果更大(确实如此)，则将其排序到列表 ((8,1), (3,0), (2,3)) 中并丢弃最小的。

一开始，前 3 名中有很多变化，但后来，它们变得很少了。当然，在遍历时，您还必须记录最后一个位置(3、4、5、...)。

前 N 个元素的插入排序应该非常高效。

Here is a similar problem in Scala但无需报告索引。