在线性时间内获取列表中的第二大数字 [英] Get the second largest number in a list in linear time

问题描述

我正在学习 Python，我认为处理列表的简单方法是一个优势.有时是这样，但看看这个:

<预><代码>>>>数字 = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]>>>numbers.remove(max(numbers))>>>最大(数字)74

从列表中获取第二大数字的一种非常简单快捷的方法.除了简单的列表处理有助于编写一个程序，该程序在列表中运行两次，找到最大的，然后是第二大的.这也是破坏性的 - 如果我想保留原始数据，我需要两份数据副本.我们需要:

<预><代码>>>>数字 = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]>>>如果数字[0]>数字[1]):... m, m2 = numbers[0], numbers[1]... 别的:... m, m2 = numbers[1], numbers[0]...>>>对于数字中的 x[2:]:...如果x＞m2:...如果x>m:... m2, m = m, x... 别的:... m2 = x...>>>平方米74

只遍历列表一次，但不像之前的解决方案那样简洁明了.

那么:在这种情况下，有没有办法同时拥有两者?第一个版本的清晰，但第二个的单次运行?

解决方案

由于@OscarLopez 和我对第二大的意思有不同的看法，我会根据我的解释并按照提供的第一个算法发布代码发问者.

def second_largest(numbers):计数 = 0m1 = m2 = float('-inf')对于 x 数字:计数 += 1如果 x >平方米:如果 x >= m1:m1, m2 = x, m1别的:米2 = x如果计数 >= 2 则返回 m2 否则无

(注意:这里使用负无穷大而不是 None，因为 None 在 Python 2 和 3 中具有不同的排序行为 - 请参阅Python - 查找第二小的数字；检查 numbers 中的元素数量可确保在实际答案时不会返回负无穷大未定义.)

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

运行相同的测试:

second_largest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])=>74第二个最大([1,1,1,1,1,2])=>1第二个最大([2,2,2,2,2,1])=>2第二个最大([10,7,10])=>10第二个最大([1,1,1,1,1,1])=>1第二大([1])=>没有任何第二大([])=>没有任何

更新

我重新构造了条件语句以显着提高性能；在我对随机数的测试中几乎达到了 100%.这样做的原因是在原始版本中，elif 总是在下一个数字不是列表中最大的情况下进行评估.换句话说，对于列表中的几乎每个数字，都进行了两次比较，而一次比较基本上就足够了——如果该数字不大于第二大，则它也不大于最大.

I'm learning Python and the simple ways to handle lists is presented as an advantage. Sometimes it is, but look at this:

>>> 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

A very easy, quick way of obtaining the second largest number from a list. Except that the easy list processing helps write a program that runs through the list twice over, to find the largest and then the 2nd largest. It's also destructive - I need two copies of the data if I wanted to keep the original. We need:

>>> 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

Which runs through the list just once, but isn't terse and clear like the previous solution.

So: is there a way, in cases like this, to have both? The clarity of the first version, but the single run through of the second?

解决方案

Since @OscarLopez and I have different opinions on what the second largest means, I'll post the code according to my interpretation and in line with the first algorithm provided by the questioner.

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

(Note: Negative infinity is used here instead of None since None has different sorting behavior in Python 2 and 3 – see Python - Find second smallest number; a check for the number of elements in numbers makes sure that negative infinity won't be returned when the actual answer is undefined.)

If the maximum occurs multiple times, it may be the second largest as well. Another thing about this approach is that it works correctly if there are less than two elements; then there is no second largest.

Running the same tests:

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

Update

I restructured the conditionals to drastically improve performance; almost by a 100% in my testing on random numbers. The reason for this is that in the original version, the elif was always evaluated in the likely event that the next number is not the largest in the list. In other words, for practically every number in the list, two comparisons were made, whereas one comparison mostly suffices – if the number is not larger than the second largest, it's not larger than the largest either.

这篇关于在线性时间内获取列表中的第二大数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！