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

Question

我正在学习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

它只运行一次列表,但不像以前的解决方案那样简洁明了.

那么:在这样的情况下,有没有办法让两者都有？第一个版本的清晰度,但第二个版本的单个运行？

Answer 1

您可以使用heapq模块:

>>> el = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> import heapq
>>> heapq.nlargest(2, el)
[90.8, 74]

从那里开始......

Answer 2

由于@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在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
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始终在下一个数字不是列表中最大的情况下进行评估.换句话说,对于列表中的几乎每个数字,进行了两次比较,而一次比较大部分就足够了 - 如果数字不大于第二大数字,则它也不大于最大值.

Answer 3

你可以随时使用 sorted

>>> sorted(numbers)[-2]
74

Answer 4

尝试下面的解决方案,它将O(n)存储并返回second变量中的第二个最大数字.请注意,如果所有元素numbers都相等,或者如果它numbers是空的或者它包含单个元素,则变量second最终会得到一个值None- 这是正确的,因为在那些情况下没有"第二大"元素.

注意:这会找到"第二个最大值",如果有多个值是"第一个最大值",它们将被视为相同的最大值 - 在我的定义中,在这样的列表中:[10, 7, 10]正确的答案是7.

def second_largest(numbers):
    first, second = None, None
    for n in numbers:
        if n > first:
            first, second = n, first
        elif first > n > second:
            second = n
    return second

以下是一些测试:

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])
=> 1
second_largest([10, 7, 10])
=> 7
second_largest([1,1,1,1,1,1])
=> None
second_largest([1])
=> None
second_largest([])
=> None

Answer 5

为什么要把场景复杂化？它非常简单直接

1. 将列表转换为集合 - 删除重复项
2. 再次将集合转换为列表 - 按升序给出列表

这是一个代码

mlist = [2, 3, 6, 6, 5]
mlist = list(set(mlist))
print mlist[-2]

Answer 6

您可以通过以下任一方式找到第二大的：

选项1：

numbers = set(numbers)
numbers.remove(max(numbers))
max(numbers)

选项2：

sorted(set(numbers))[-2]