Python - 找到第二小的数字 [英] Python - Find second smallest number

问题描述

我在这个网站上找到了这个代码来找到第二大的数字:

def second_largest(numbers):m1, m2 = 无, 无对于 x 数字:如果 x >= m1:m1, m2 = x, m1elif x >平方米:米2 = x返回 m2

来源:获取第二大数在线性时间的列表中

是否可以修改此代码以找到第二个最小数字?所以例如

print second_smallest([1, 2, 3, 4])2

解决方案

确实可以修改函数来找第二小的:

def second_smallest(numbers):m1 = m2 = float('inf')对于 x 数字:如果 x <= m1:m1, m2 = x, m1elif x <平方米:米2 = x返回 m2

旧版本依赖于 Python 2 实现细节，即 None 总是排在其他任何东西之前(因此它测试为更小")；我用 float('inf') 作为标记替换了它，因为无穷大总是测试为 大于 比任何其他数字.理想情况下，原始函数应该使用 float('-inf') 而不是 None，以免与其他 Python 实现可能不共享的实现细节相关联.>

演示:

<预><代码>>>>def second_smallest(数字):... m1 = m2 = float('inf')... 对于 x 数字:...如果 x <= m1:... m1, m2 = x, m1... elif x <平方米:... m2 = x...返回 m2...>>>打印(second_smallest([1, 2, 3, 4]))2

在您发现的函数之外，使用 heapq.nsmallest() 函数 从可迭代对象中返回两个最小值，并从这两个值中选择第二个(或最后一个)值.我已经包含了 unique_everseen()配方过滤掉重复的数字:

from heapq import nsmallest从 itertools 导入 filterfalsedef second_smallest(数字):s = 设置()sa = s.addun = (sa(n) or n for n in filterfalse(s.__contains__, numbers))返回 nsmallest(2, un)[-1]

和上面的实现一样，这是一个O(N)的解决方案；保持堆变量的每一步都需要 logK 时间，但这里的 K 是一个常数 (2)！

无论你做什么，不要使用排序；这需要 O(NlogN) 时间.

I found this code on this site to find the second largest number:

def second_largest(numbers):
    m1, m2 = None, None
    for x in numbers:
        if x >= m1:
            m1, m2 = x, m1
        elif x > m2:
            m2 = x
    return m2

Source: Get the second largest number in a list in linear time

Is it possible to modify this code to find the second smallest number? So for example

print second_smallest([1, 2, 3, 4])
2

解决方案

The function can indeed be modified to find the second smallest:

def second_smallest(numbers):
    m1 = m2 = float('inf')
    for x in numbers:
        if x <= m1:
            m1, m2 = x, m1
        elif x < m2:
            m2 = x
    return m2

The old version relied on a Python 2 implementation detail that None is always sorted before anything else (so it tests as 'smaller'); I replaced that with using float('inf') as the sentinel, as infinity always tests as larger than any other number. Ideally the original function should have used float('-inf') instead of None there, to not be tied to an implementation detail other Python implementations may not share.

Demo:

>>> def second_smallest(numbers):
...     m1 = m2 = float('inf')
...     for x in numbers:
...         if x <= m1:
...             m1, m2 = x, m1
...         elif x < m2:
...             m2 = x
...     return m2
... 
>>> print(second_smallest([1, 2, 3, 4]))
2

Outside of the function you found, it's almost just as efficient to use the heapq.nsmallest() function to return the two smallest values from an iterable, and from those two pick the second (or last) value. I've included a variant of the unique_everseen() recipe to filter out duplicate numbers:

from heapq import nsmallest
from itertools import filterfalse

def second_smallest(numbers):
    s = set()
    sa = s.add
    un = (sa(n) or n for n in filterfalse(s.__contains__, numbers))
    return nsmallest(2, un)[-1]

Like the above implementation, this is a O(N) solution; keeping the heap variant each step takes logK time, but K is a constant here (2)!

Whatever you do, do not use sorting; that takes O(NlogN) time.

这篇关于Python - 找到第二小的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！