在线性时间内得到一个列表中的第二大数字。

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

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

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:

从列表中获取第二大数字的一种非常简单、快捷的方法。除了简单的列表处理帮助编写一个遍历列表两次的程序，查找最大的和第2大的程序。它也具有破坏性——如果我想保留原文，我需要两份数据。我们需要:

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

所以:在这种情况下，两者都有吗?第一个版本的清晰性，但是第二个版本贯穿始终?

15 个解决方案

#1

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

因为@OscarLopez和我对于第二大的方法有不同的看法，我将根据我的视觉来发布代码，并与asker提供的第一个算法相一致。

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

(注意:这里用的是负无穷大，而不是没有，因为在Python 2和3中没有任何不同的排序行为——参见Python——找到第二个最小的数字;检查数字中的元素数量，确保在未定义实际答案时不会返回负无穷。

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.

我对条件进行了调整，以显著提高性能;几乎是100%在我的随机数测试中。这样做的原因是，在最初的版本中，elif总是在可能的事件中进行评估，而下一个数字并不是列表中最大的。换句话说，对于列表中的每一个数字，都有两种比较，而一种比较基本满足——如果数字不大于第二大，也不大于最大。

#2

You could use the heapq module:

你可以使用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]

And go from there...

从那里去……

#3

You could always use sorted

你可以一直用排序。

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

#4

Try the solution below, it's O(n) and it will store and return the second greatest number in the second variable. Notice that if all elements in numbers are equal, or if numbers is empty or if it contains a single element, the variable second will end up with a value of None - this is correct, as in those cases there isn't a "second greatest" element.

尝试下面的解决方案，它是O(n)，它将存储并返回第二个变量中第二个最大的数字。请注意，如果数字中的所有元素都是相等的，或者如果数字是空的，或者如果它包含一个元素，那么变量秒就会以None值结束——这是正确的，因为在那些情况下，没有一个“第二大”元素。

Beware: this finds the "second maximum" value, if there's more than one value that is "first maximum", they will all be treated as the same maximum - in my definition, in a list such as this: [10, 7, 10] the correct answer is 7.

注意:如果有超过一个值是“第一个最大值”，那么它们将被视为相同的最大值——在我的定义中，在这样的列表中:[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

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

#5

>>> l = [19, 1, 2, 3, 4, 20, 20]
>>> sorted(set(l))[-2]
19

#6

The quickselect algorithm, O(n) cousin to quicksort, will do what you want. Quickselect has average performance O(n). Worst case performance is O(n^2) just like quicksort but that's rare, and modifications to quickselect reduce the worst case performance to O(n).

快速选择算法，O(n)快速排序的表兄，会做你想做的。快速选择具有平均性能O(n)。坏的情况下性能是O(n ^ 2)就像快速排序但少见,和修改quickselect减少O(n)最坏情况下的性能。

The idea of quickselect is to use the same pivot, lower, higher idea of quicksort, but to then ignore the lower part and to further order just the higher part.

快速选择的想法是使用相同的主元，更低的，更高的快速排序的概念，但是忽略较低的部分，并进一步的顺序，只是更高的部分。

#7

Why to complicate the scenario? Its very simple and straight forward

为什么要把这种情况复杂化呢?它非常简单直接。

Convert list to set - removes duplicates
转换列表来设置-删除重复。
Convert set to list again - which gives list in ascending order
转换集重新列表-该列表按升序排列。

Here is a code

这是一个代码

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

#8

there are some good answers here for type([]), in case someone needed the same thing on a type({}) here it is,

对于type([])，这里有一些很好的答案，如果在类型({})中需要相同的东西，那么，

def secondLargest(D):
    def second_largest(L):  
        if(len(L)<2):
            raise Exception("Second_Of_One")
        KFL=None #KeyForLargest
        KFS=None #KeyForSecondLargest
        n = 0
        for k in L:
            if(KFL == None or k>=L[KFL]):
                KFS = KFL
                KFL = n
            elif(KFS == None or k>=L[KFS]):
                KFS = n
            n+=1
        return (KFS)
    KFL=None #KeyForLargest
    KFS=None #KeyForSecondLargest
    if(len(D)<2):
        raise Exception("Second_Of_One")
    if(type(D)!=type({})):
        if(type(D)==type([])):
            return(second_largest(D))
        else:
            raise Exception("TypeError")
    else:
        for k in D:
            if(KFL == None or D[k]>=D[KFL]):
                KFS = KFL               
                KFL = k
            elif(KFS == None or D[k] >= D[KFS]):
                KFS = k
    return(KFS)

a = {'one':1 , 'two': 2 , 'thirty':30}
b = [30,1,2] 
print(a[secondLargest(a)])
print(b[secondLargest(b)])

Just for fun I tried to make it user friendly xD

只是为了好玩，我试着让它成为用户友好的xD。

#9

n=input("Enter a list:")
n.sort()
l=len(n)
n.remove(n[l-1])
l=len(n)
print n[l-1]

#10

You can also try this:

你也可以试试:

>>> list=[20, 20, 19, 4, 3, 2, 1,100,200,100]
>>> sorted(set(list), key=int, reverse=True)[1]
100

#11

O(n): Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount. For example following functions have O(n) time complexity.

O(n):如果循环变量以不变的量递增/递减，则将循环的时间复杂度视为O(n)。例如，以下函数有O(n)时间复杂度。

 // Here c is a positive integer constant   
   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

To find the second largest number i used the below method to find the largest number first and then search the list if thats in there or not

为了找到第二大的数字，我用下面的方法先找到最大的数字，然后再搜索列表，如果有的话。

x = [1,2,3]
A = list(map(int, x))
y = max(A)
k1 = list()
for values in range(len(A)):
if y !=A[values]:
    k.append(A[values])

z = max(k1)
print z

#12

If you do not mind using numpy (import numpy as np):

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

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

gives you the 2nd largest element of the list with a guaranteed worst-case O(n) running time.

给出列表的第2大元素，保证最坏情况下(n)运行时间。

The partition(a, kth) methods returns an array where the kth element is the same it would be in a sorted array, all elements before are smaller, and all behind are larger.

该分区(a, kth)方法返回一个数组，其中第k个元素是相同的，它将在一个有序数组中，所有元素之前都是较小的，后面的所有元素都更大。

#13

Objective: To find the second largest number from input.

目的:从输入中找到第二大数字。

Input : 5 2 3 6 6 5

输入:5 2 3 6 6 5。

Output: 5

输出:5

*n = int(raw_input())
arr = map(int, raw_input().split())
print sorted(list(set(arr)))[-2]*

#14

This can be done in [N + log(N) - 2] time, which is slightly better than the loose upper bound of 2N (which can be thought of O(N) too).

这可以在[N + log(N) - 2]时间内完成，这比2N的松散上限稍好(也可以考虑O(N))。

The trick is to use binary recursive calls and "tennis tournament" algorithm. The winner (the largest number) will emerge after all the 'matches' (takes N-1 time), but if we record the 'players' of all the matches, and among them, group all the players that the winner has beaten, the second largest number will be the largest number in this group, i.e. the 'losers' group.

诀窍是使用二进制递归调用和“网球锦标赛”算法。获胜者(最多)将出现在所有的“匹配”(n - 1),但是如果我们记录的球员的比赛,其中,集团所有的球员,获胜者殴打,第二大数量将在这组最多,即“失败者”。

The size of this 'losers' group is log(N), and again, we can revoke the binary recursive calls to find the largest among the losers, which will take [log(N) - 1] time. Actually, we can just linearly scan the losers group to get the answer too, the time budget is the same.

这个“失败者”组的大小是log(N)，再一次，我们可以取消二进制递归调用，以找到最大的失败者，这将占用[log(N) - 1]时间。实际上，我们可以线性扫描输家组得到答案，时间预算是一样的。

Below is a sample python code:

下面是一个示例python代码:

def largest(L):
    global paris
    if len(L) == 1:
        return L[0]
    else:
        left = largest(L[:len(L)//2])
        right = largest(L[len(L)//2:])
        pairs.append((left, right))
        return max(left, right)

def second_largest(L):
    global pairs
    biggest = largest(L)
    second_L = [min(item) for item in pairs if biggest in item]

    return biggest, largest(second_L)  



if __name__ == "__main__":
    pairs = []
    # test array
    L = [2,-2,10,5,4,3,1,2,90,-98,53,45,23,56,432]    

    if len(L) == 0:
        first, second = None, None
    elif len(L) == 1:
        first, second = L[0], None
    else:
        first, second = second_largest(L)

    print('The largest number is: ' + str(first))
    print('The 2nd largest number is: ' + str(second))

#15

A simple way :

一个简单的方法:

n=int(input())
arr = set(map(int, input().split()))
arr.remove(max(arr))
print (max(arr))

#1