python练习题-寻找列表里第二大的数

题目要求

实现算法，查找列表里第二大的数

lst = [3, 6, 7, 9, 2]

思路分析

最直接的方法是使用列表的sort方法，从小到大排序，lst.sort()，lst[-2] 就是列表里第2大的数。

能想到这个处理方法，对初学者来说，很好了，如果要求算法复杂度为O(n) 呢？ 显然，排序算法都不符合要求。

找列表里最大值，只需要遍历一遍列表就可以实现，算法复杂度是O(n)， 能否以此为基础，顺带手的找出列表里第2大的数呢？

设置两个变量，max_value,sec_max_value，分别表示列表里的最大值和第2大的值，遍历列表，分别于他们比较并进行替换，

示例代码

lst = [3, 6, 7, 9, 2]

max_value = lst[0]
sec_max_value = lst[1]

# 先假设列表里前两个数据是最大的和第二大的
if sec_max_value > max_value:
    max_value, sec_max_value = sec_max_value, max_value

# 遍历列表
for item in lst:
    # 小于等于第2大的数
    if item <= sec_max_value:
        continue

    # 大于第2大的数，小于等于最大的数
    if sec_max_value < item <= max_value:
        sec_max_value = item

    # 大于最大的数
    if item > max_value:
        sec_max_value = max_value
        max_value = item

print(max_value, sec_max_value)