Python - 查找第二小的数

Question

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

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

来源: 在线获取列表中第二大的数字

是否可能修改这段代码以查找第二个最小数字？例如：

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

- user2971812

---

我猜这只是用作练习，对吧？否则，像sorted(numbers)[1]这样的代码可能更可取。 - Tim Pietzcker

@MartijnPieters：好的，我没有想到使用heapq。 - Tim Pietzcker

@TimPietzcker：仅适用于小于约10k个元素的列表；从算法上讲，这里的方法是O(N)，而heapq和sorted分别需要O(NlogK)和O(NlogN)，但C的速度在这里胜出算法。 - Martijn Pieters

@gnibbler：然而，这个轮子现在已经供人们使用了。 - Martijn Pieters

@schneck：这还不是回答“我该如何修改此函数以返回第二小的元素”的问题。 - Martijn Pieters

Answer 1

a = [6,5,4,4,2,1,10,1,2,48]
s = set(a) # used to convert any of the list/tuple to the distinct element and sorted sequence of elements
# Note: above statement will convert list into sets 
print sorted(s)[1] 

- Nita Mandavkar

---

虽然答案可能是正确的，请添加一些解释而不仅仅是代码转储。另外，如果我可以补充的话，请尝试格式化您的代码，以便代码行之间没有空白行。 - nbryans

在这种情况下，代码非常简单和自解释性强，文字解释不会增加任何有用的内容。 - cmrichards

我同意，这里很容易理解：sorted(set(a))[1]。 - Basj

然而，将所有数字按精确排序是浪费CPU周期的。而且它并没有回答所提出的问题：是否可以修改此代码... - Martijn Pieters

Answer 2

这个函数确实可以被修改以找到第二小的:

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

旧版本依赖于Python 2的一个实现细节，即None总是在其他所有内容之前排序（因此它测试时会被认为“更小”）; 我用float('inf')作为哨兵替换了它，因为无限大始终测试为比任何其他数字都要大。理想情况下，原始函数应该在那里使用float('-inf')而不是None，以不被绑定到其他Python实现可能不共享的实现细节。

演示：

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

除了找到的那个函数以外，使用heapq.nsmallest()函数从一个可迭代对象中返回两个最小值，然后从这两个值中选择第二个（或最后一个）是几乎同样有效的。我包含了变体unique_everseen() recipe来过滤出重复的数字：

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]

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

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

- Martijn Pieters

---

@MartijnPieters 对于列表 [1, 2, 3, 4, 5, 1]，它返回的是1而不是2。请参见http://stackoverflow.com/a/32829246/793428 - Ozgur Vatansever

@ozgur：1或2哪个是第二小的是有争议的。当排序时，“1”既是序列中的第一个值，也是第二个值。 - Martijn Pieters

如果数组只有一个值 [0]，那么它会失败，并返回 float('inf')。 - RegarBoy

@开发者：如果一个名为second_smallest()的函数针对只有一个值的列表返回什么，你期望它会返回什么？我认为在这种情况下float('inf')恰好是正确的答案，或者你可以在顶部放置一个测试，如果只有一个元素则抛出异常。 - Martijn Pieters

Python 3.6+，使用un={}.fromkeys(numbers).keys()更容易对列表进行去重（并保持顺序）。 - dawg

Answer 3

或者只需使用heapq：

import heapq
def second_smallest(numbers):
    return heapq.nsmallest(2, numbers)[-1]

second_smallest([1, 2, 3, 4])
# Output: 2

- John La Rooy

---

这是O(NlogK)，比sorted()的O(NlogN)稍微好一点。它能够击败O(N)算法，直到你处理大约10k个元素，因为heapq使用了C优化。 - Martijn Pieters

仅供参考：这实际上并不是对所述问题的答案。 - Martijn Pieters

嗯，我通过删除7行并添加2行进行了修改。 - John La Rooy

您的函数名称和实现冲突（largest vs smallest），并且您正在忽略numbers参数。 - Martijn Pieters

Answer 4

根据Python内置函数sorted：

sorted(my_list)[0]

该函数返回最小的数，sorted(my_list)[1] 取出第二小的数，以此类推。

- gented

---

如果列表是 [19, 19, 20, 21]，那么这是如何工作的？ 如果我选择 x[1]，我仍然会得到最小的数字。 - paradd0x

sorted(list(set(my_list)))[1] - boldbrandywine

@boldbrandywine sorted(list(set))，为什么需要额外的列表<->集合转换？可以删除列表转换。 - Reishin

为什么要对所有数字进行排序，当你只需要最小的两个值呢？ - Martijn Pieters

Answer 5

我最喜欢找到第二小的数字的方法是从列表中排除最小的数字，然后打印列表中的最小值，这样就能返回列表的第二小元素。以下是该任务的代码：

mylist=[1,2,3,4]
mylist=[x for x in mylist if x!=min(mylist)]  #deletes the min element from the list
print(min(mylist))

- Mayank Gubba

---

这个程序的时间复杂度为O(N^2)（平方），因为min(mylist)在mylist中的每个值上都被执行了一次。首先将最小值赋值给一个变量，这样它只会被计算一次，而且不要创建一个新的列表：m = min(mylist)，然后second_smallest = min(v for v in mylist if v != m)。 - Martijn Pieters

Answer 6

返回列表中第二个唯一数字的解决方案，不排序：

def sec_smallest(numbers):
    smallest = float('+inf')
    small = float('+inf')
    for i in numbers:
        if i < smallest:
            small = smallest
            smallest = i
        elif i < small and i != smallest:
            small = i
    return small

print('Sec_smallest:', sec_smallest([1, 2, -8, -8, -2, 0]))

- helenko11

---

这个与我的实现有什么不同之处？ - Martijn Pieters

Answer 7

在整数数组中找到第一个和第二个最小的数字

arr= [1,2,3,4,5,6,7,-1,0,-2,-10]
def minSecondmin(arr,n):
  i=1
  if arr[i-1] < arr[i]:
    f = arr[i-1]
    s = arr[i]
  else:
    f=arr[i]
    s=arr[i-1]

  for i in range(2,n):
    if arr[i]<f:
      s=f
      f = arr[i]
    elif arr[i]<s:
      s=arr[i]
  return f,s

minSecondmin(arr,len(arr))

- Wais Yousofi

Answer 8

你可能会觉得这段代码很简单易懂

def secsmall(numbers):
small = max(numbers)
for i in range(len(numbers)):
    if numbers[i]>min(numbers):
        if numbers[i]<small:
            small = numbers[i]
return small

我假设“numbers”是一个列表名称。

- D Sai Krishna

Answer 9

我想添加另一种更普遍的方法：
以下是一种递归查找给定数字列表中第i个最小值的方法

def find_i_minimums(numbers,i):
    minimum = float('inf')
    if i==0:
        return []
    less_than_i_minimums = find_i_minimums(numbers,i-1)
    for element in numbers:
        if element not in less_than_i_minimums and element < minimum:
            minimum = element
    return less_than_i_minimums + [minimum]

例如，

>>> find_i_minimums([0,7,4,5,21,2,6,1],3) # finding 3 minimial values for the given list
[0, 1, 2]

（如果你只想要第i小的数，你需要提取列表的最终值）

尽管上述算法的时间复杂度很差，为O(N*i^2)（因为递归深度为i，在每个递归调用中我们会遍历长度为N的'numbers'列表中的所有值，并检查我们正在搜索的最小元素是否不在长度为i-1的列表中，因此总复杂度可以用一个几何级数来描述，它将给出上述提到的复杂度）。

这里有一个类似但另一种实现方法，其平均时间复杂度为O(N*i)，它使用了Python内置的'set'数据结构：

def find_i_minimums(numbers,i):
    minimum = float('inf')
    if i==0:
        return set()
    less_than_i_minimums = find_i_minimums(numbers,i-1)
    for element in numbers:
        if element not in less_than_i_minimums and element < minimum:
            minimum = element
    return less_than_i_minimums.union(set({minimum}))

如果你的'i'很小，你可以使用上面的实现，然后提取你想要的最小值（或者如果你想要第二个最小值，在你的情况下运行i=2的代码，然后只需从输出数据结构中提取最后一个元素）。 但是，如果'i'比log(N)大，我建议对数字列表进行排序（例如，使用归并排序，其复杂度在最坏情况下为O(N*log(N)）），然后取第i个元素。为什么呢？因为如上所述，上述算法的运行时间对于较大的'i'值不太理想。

- jacob12

Answer 10

是的，除了代码依赖于一个小技巧（在Python 3中引发异常）：即 None 比数字更小。

另一个可用的值是 float("-inf")，它是比任何其他数字都小的数字。

如果您使用它而不是 None，并将 -inf 更改为 +inf，将 > 更改为 <，那么它就可以正常工作。

编辑：另一种可能性是在所有关于 x 的比较中简单地写入 -x，例如执行 if -x <= m1: 等等。

- RemcoGerlich

---

不仅仅是一个怪癖，而是一种实现细节。这是 Python 2 要求异构序列可排序的结果，因此必须做出选择，其中 None 排序。然而，这个选择是任意的。 - Martijn Pieters