在 Python 中查找列表中第二大项的更有效方法

Question

我编写了这个简单的代码，用于执行查找整数列表中第二大项的简单任务：

def second_largest(input_list):
  input_list.sort()
  return input_list[-2]

然而，对于大型列表，此功能可能非常无效，例如一百万个项目的运行时间超过 1.5 秒。

我知道这是因为该函数更改了列表本身（使用 .sort 方法），这对于长列表来说可能非常低效。如何执行此任务，而不必使用更改列表的低效方法？

提前谢谢大家。

Answer 1

怎么样：

lst = list(range(1000000))

largest, second_largest = sorted(lst[:2])
for x in lst[2:]:
    if x > largest:
        largest, second_largest = x, largest
    elif x > second_largest:
        second_largest = x
print(largest, second_largest) # 999999 999998

它只遍历一个可迭代对象一次，所以我希望它是高效的。（这假设列表至少有两项。）