获取线性时间列表中的第二大数字

一尘不染

获取线性时间列表中的第二大数字

python

我正在学习Python，而处理列表的简单方法是一种优势。有时是这样，但请看以下内容：

>>> numbers = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> numbers.remove(max(numbers))
>>> max(numbers)
74

从列表中获取第二大数字的一种非常简单，快速的方法。除了简单的列表处理之外，还可以编写一个遍历列表两次的程序，以找到最大的程序，然后找到第二大的程序。这也是破坏性的-如果我想保留原始数据，则需要两个数据副本。我们需要：

>>> numbers = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> if numbers[0]>numbers[1]):
...    m, m2 = numbers[0], numbers[1]
... else:
...    m, m2 = numbers[1], numbers[0]
...
>>> for x in numbers[2:]:
...    if x>m2:
...       if x>m:
...          m2, m = m, x
...       else:
...          m2 = x
...
>>> m2
74

该列表仅运行一次，但并不像以前的解决方案那样简洁明了。

那么：在这种情况下，有没有办法让两者兼而有之？第一个版本的清晰度很高，但是第二个版本是否单次运行？

阅读 136

2020-12-20

共1个答案

一尘不染

由于@OscarLopez和我对第二大含义是什么有不同的看法，因此我将根据自己的解释并按照发问者提供的第一种算法发布代码。

def second_largest(numbers):
    count = 0
    m1 = m2 = float('-inf')
    for x in numbers:
        count += 1
        if x > m2:
            if x >= m1:
                m1, m2 = x, m1            
            else:
                m2 = x
    return m2 if count >= 2 else None

（注意：此处使用负无穷大，而不是None因为None在Python2和3中具有不同的排序行为-请参阅Python-查找第二个最小的数字；检查其中的元素数numbers可确保当实际的负无穷大时不会返回答案是不确定的。）

如果最大值多次出现，那么它可能也是第二大最大值。关于这种方法的另一件事是，如果元素少于两个，则它可以正常工作；那么没有第二大的。

运行相同的测试：

second_largest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])
=> 74
second_largest([1,1,1,1,1,2])
=> 1
second_largest([2,2,2,2,2,1])
=> 2
second_largest([10,7,10])
=> 10
second_largest([1,1,1,1,1,1])
=> 1
second_largest([1])
=> None
second_largest([])
=> None

更新资料

我对条件进行了重组，以大大提高性能。在我对随机数的测试中几乎达到了100％。原因是在原始版本中，elif总是在下一个数字不是列表中最大数字的情况下对进行评估。换句话说，对于列表中的几乎每个数字，都进行了两次比较，而一次比较就足够了–如果该数字不大于第二大数字，那么它也不大于第二大数字。

2020-12-20