时间戳

首页 > 解决方案 > 如何更有效地获取列表的所有记录最高数字的索引值？

python - 如何更有效地获取列表的所有记录最高数字的索引值？

问题描述

假设我有第一个清单：

list = [0, 1, 0, 4, 3, 1, 2, 5, 1, 12, 9, 32, 31, 19, 44, 3]

以及第一个列表中所有数字 n 的第二个列表，使得 n = max(list[:n])，如下所示：

list_max = [0, 1, 4, 5, 12, 32, 44]

假设我想获取 list_max 在列表中的索引位置列表，它应该等于：

list_max_pos = [0, 1, 3, 7, 9, 11, 14]

我可以做类似的事情：

list_max_pos = []
m = len(list_max)
for n in range (0, m):
    list_max_pos.append(list.index(list_max[n]))

问题是如果原始列表非常长，即数百万个值，这将变得非常低效，因为它每次都从头开始搜索。为了节省时间，我可以开始搜索每个新值的索引，其中最后一个值的索引停止了。也就是说，在列表的第11位找到32后，我可以从第12位开始搜索44，而不是从0开始。

我将如何实现这一点？

标签： python

解决方案

在您浏览列表时，只需遍历列表一次存储索引值。这将在O(n)时间复杂度上起作用。

inputlist = [0, 1, 0, 4, 3, 1, 2, 5, 1, 12, 9, 32, 31, 19, 44, 3]
maxvalue = -1
answer= []
for index,element in enumerate(inputlist):
    if element > maxvalue:
        maxvalue = element
        answer.append(index)
print(answer)

注意： 插入到列表中的摊销时间复杂度O(1)。插入的渐近最坏情况运行时间复杂度为O(n)，平均情况为O(1)。您可以使用出队来稍微加快速度。插入出队的渐近和摊销的最坏情况运行时间复杂度为O(1).

您可以在此处阅读更多相关信息 -> Python 数据结构的时间复杂性

输出

[0, 1, 3, 7, 9, 11, 14]

推荐阅读