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

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

有一种方法可以同时拥有第一个版本的清晰度和第二个版本的单次运行吗？但并非像前一个解决方案那样简洁明了。

- boisvert

---

我认为你的第二种方法（O(N)）是最好的，因为对于大型列表而言，仅仅因为代码短小就使用一行代码并不是一个好主意。 - Ashwini Chaudhary

两次遍历列表真的是个问题吗？这仍然是O(N)，当你处理的情况算法复杂度已经足够好（或N很小）时，对性能的猜测几乎无用。你需要以多种方式编写它，并为每个版本计时（并在所有你关心的平台/实现上执行）。而且，除非这是一个瓶颈，否则这不值得花费那么多功夫。 - abarnert

现在，如果第一个元素最大，那么m2将只是最大的。我认为它也没有在m2<x<m时替换m2。 - Volatility

@boisvert：但是对于这个玩具示例正确的答案可能不会是 - 也很可能不是 - 对于类似的实际情况正确的答案。例如，如果您需要在继续添加到列表时重复获取前两个元素，则可能希望随着操作的进行跟踪前两个元素，并在每次添加时检查，或者保持列表连续排序（例如，使用基于树的集合如 blist.sortedlist 而不是列表）。 - abarnert

@abarnert，所以“跟踪前两个”是O（N）解决方案 - 除了循环等待输入 - 而“持续排序”是不同的要求。虽然为了保持排序，我可以想象有人会在每次新输入时将“排序”应用于列表：再次，简单的解决方案是差劲的。 - boisvert

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]

从那里开始...

- Jon Clements

---

相当于：sorted(iterable,reverse=True)[:n]，仍为 NlogN。 - Ashwini Chaudhary

是的，它在功能上等价于那个；但是，由于其实现方式，它进行的比较更少，因此比排序和切片更有效。 - Jon Clements

@JonClements：但是对于大的N，O(NlogN)仍然远远不及O(N)好，而且原帖已经有了一个O(N)的解决方案，这就是（我认为）Ashwini指出的。 - abarnert

经过简单测试，在我的 Mac 上使用 64 位 CPython 3.3.0，交叉点大约在 N=1000000 左右。在此之上，原始代码的速度显著更快；在此之下，则相反。 - abarnert

@Zakaria，我显然没有暗示它们是相同的，但说Nlog(N)比N差得多是非常不正确的，即使O(N)可以是N的任意倍数，鉴于logN的增长速度极慢，NlogN的解决方案仍然更可取。此外，这是对上面评论的回复：“但是对于大N，O(NlogN)仍然远远不及O(N)好，而且OP已经有了一个O(N)的解决方案，这就是（我认为）Ashwini所指出的。” - Abhishek Choudhary

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

(Note: 这里使用负无穷代替None，因为在Python 2和3中，None的排序行为不同 - 详见Python - Find second smallest number；检查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 总是被评估。换句话说，在列表中的几乎每个数字都会进行两次比较，而一次比较通常就足够了——如果数字不大于第二大的数字，则它也不会大于最大的数字。

- Thijs van Dien

---

这个功能与查找最大值、删除和查找其余部分的最大值相同。 - boisvert

@OscarLopez list.remove() 只会删除第一个匹配的元素。 - Thijs van Dien

你不应该依赖于Python 2的实现细节；None的排序顺序是任意选择的。请使用float('inf')代替。 - Martijn Pieters

@MartijnPieters 函数在答案实际上未定义时，不应返回负无穷大（可能存在的数字）。已更新答案以考虑此情况。 - Thijs van Dien

@ShivamBharadwaj 阅读完整个答案，你会发现它按预期工作。 - Thijs van Dien

Answer 3

您可以始终使用sorted。

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

- Volatility

---

我不明白为什么人们会接受这种方法，它不仅不是 O(N)，甚至与之前的算法完全不同。它只是对数组进行排序然后选择倒数第二个元素，如果存在多个最大值，它将给出错误的答案。你需要在排序后再使用另一个循环来选择真正的第二大元素，这是不好的，因为已经存在 O(N) 的解决方案。 - Abhishek Choudhary

Answer 4

尝试以下解决方案，它的时间复杂度为O(n)，并将第二大的数字存储在变量second中返回。 更新：我已经调整了代码以适用于Python 3，因为现在对None进行算术比较无效。

请注意，如果numbers中所有元素相等，或者numbers为空或者它只包含一个元素，则变量second最终将具有None的值-在这些情况下没有“第二个最大”的元素。

注意：这会找到“第二大”的值，如果存在多个值是“第一大”，它们都将被视为相同的最大值-根据我的定义，在类似于这样的列表中：[10, 7, 10]，正确答案是7。

def second_largest(numbers):
    minimum = float('-inf')
    first, second = minimum, minimum
    for n in numbers:
        if n > first:
            first, second = n, first
        elif first > n > second:
            second = n
    return second if second != minimum else None

这里是一些测试：

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

- Óscar López

---

如果最大值出现了多次，就会出错。应该是 if n >= first。或者我们将重复的值视为一个？ - Thijs van Dien

第二个条件：elif first > n > second: second = n 永远不会被满足，因此应该被删除。 - Roy learns to code

这会出现错误 TypeError: '>' 不支持 'int' 和 'NoneType' 实例之间的比较。 - Nikhil Talreja

@NikhilTalreja 是针对什么输入数据？也许你的数组中有 None 值？ - Óscar López

@NikhilTalreja 感谢您报告了这个错误！我已经使用修复程序更新了我的代码，并添加了您的测试案例。该错误开始发生在 Python 3 中，因为现在我们不能对 None 进行算术比较。 - Óscar López

Answer 5

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

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

选项2：

sorted(set(numbers))[-2]

- Sahil Chhabra

Answer 6

这是一种简单的方法之一

def find_second_largest(arr):
    first, second = float('-inf'), float('-inf')

    for number in arr:
        if number > first:
            second = first
            first = number
        elif second < number < first:
            second = number

    return second

- Ganesh Patil

---

很遗憾，如果所有数字都小于零，则此解决方案无法工作。 - Michael Berdyshev

我已经编辑了脚本...希望现在能按预期工作 @MichaelBerdyshev - Ganesh Patil

Answer 7

快速选择算法是快速排序的O(n)版本，可以满足你的需求。快速选择算法的平均性能为O(n)，最坏情况下的性能与快速排序一样是O(n^2)，但这种情况很少发生，对快速选择算法进行修改可以将最坏情况的性能降至O(n)。

快速选择算法的思想与快速排序相同，都是使用相同的枢轴、低位和高位的概念，但快速选择算法会忽略低位并进一步对高位进行排序。

- Edward Doolittle

---

@edward_doolittle，这是一个非常有趣的想法。我最初的问题之一是高效的解决方案并不“整洁”。更通用的算法意味着实现中不那么整洁的部分可以被分解掉，至少在这种情况下是这样。 - boisvert

这是在numpy.partition中使用的（实际上，它是introselect算法，可以升级quickselect）。请参见例如https://dev59.com/3WQo5IYBdhLWcg3wOdJa#43171040。 - serv-inc

Answer 8

为什么要让场景变复杂？这很简单而且直接。

1. 将列表转换为集合——去除重复项
2. 再将集合转换为列表——可以按升序排列

下面是示例代码：

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

- Abhishek Kulkarni

---

问题在于这些操作所花费的时间（顺便说一下，重复项不是我的第一个问题）。排序操作的时间复杂度为 O(n*log(n))，但是查找最大值（不排序）是线性的（O(n)），因为它只需要一次循环。一个朴素的解决方案需要两个循环：O(2n)。一个不那么朴素的解决方案应该只需一次循环，在一次遍历中寻找最大值和次大值。我的真正问题——这里没有得到真正的回答——是这样的：单次遍历解决方案很难理解和编写，换句话说，Python 并不擅长使复杂处理变得简单易懂，尽管我们常常这样说。 - boisvert

将集合再次转换为列表 - 以升序给出列表。需要引用... list({400, 2, 100})会返回 [400，2，100]，所以我不确定这怎么回答问题...（也许对于特定的小整数可以工作，但并非总是如此） - Tomerikoo

@Tomerikoo 这只是错误的假设。列表构建不会对元素进行排序。 - Michael Berdyshev

Answer 9

如果您不介意使用numpy (import numpy as np):

np.partition(numbers, -2)[-2]

这个功能能够以O(n)的最坏情况运行时间，给出列表中第二大的元素。

partition(a, kth)方法返回一个数组，其中k元素在排序后与原数组相同，前面的元素都比它小，后面的元素都比它大。

- serv-inc

Answer 10

    def SecondLargest(x):
        largest = max(x[0],x[1])
        largest2 = min(x[0],x[1])
        for item in x:
            if item > largest:
               largest2 = largest
               largest = item
            elif largest2 < item and item < largest:
               largest2 = item
        return largest2
    SecondLargest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])

- Mike