如何在列表中找到第二大数字？

So I have to find the second largest number from list. I am doing it through simple loops.

所以我必须从列表中找到第二大数字。我是通过简单的循环来完成的。

My approach is to divide a list into two parts and then find the largest number into two parts and then compare two numbers. I will choose the smaller number from two of them. I can not use ready functions or different approaches.

我的方法是将列表分成两部分，然后将最大的数字分成两部分，然后比较两个数字。我将从其中两个中选择较小的数字。我不能使用现成的功能或不同的方法。

Basically, this is my code. But it does not run correctly

基本上，这是我的代码。但它运行不正常

#!/usr/local/bin/python2.7

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
largest=alist[0]
h=len(alist)/2 
m=len(alist)-h

print(alist)

for i in alist:
    if alist[h]>largest:
      largest=alist[h]
      i=i+1
print(largest)

11 个解决方案

#1

O(n^2) algorithm:

O（n ^ 2）算法：

In [79]: alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]

In [80]: max(n for n in alist if n!=max(alist))
Out[80]: 100

O(n) algorithm:

O（n）算法：

In [81]: alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]

In [82]: M = max(alist)

In [83]: max(n for n in alist if n!=M)
Out[83]: 100

#2

You don't have to sort the input, and this solution runs in O(n). Since your question says you cannot use builtin functions, you can use this

您不必对输入进行排序，此解决方案在O（n）中运行。由于你的问题说你不能使用内置函数，你可以使用它

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
largest, larger = alist[0], alist[0]

for num in alist:
    if num > largest:
        largest, larger = num, largest
    elif num > larger:
        larger = num
print larger

Output

产量

100

Keep track of the largest number and the second largest number (larger variable stores that in the code). If the current number is greater than the largest, current number becomes the largest, largest becomes just larger.

跟踪最大数字和第二大数字（代码中的较大变量存储）。如果当前数字大于最大值，则当前数字变为最大，最大变为更大。

largest, larger = num, largest is a shortcut for

最大，更大= num，最大是快捷方式

temp = largest
largest = num
larger = temp

Edit: As per OP's request in the comments,

编辑：根据评论中OP的要求，

def findLarge(myList):
    largest, larger = myList[0], myList[0]
    for num in myList:
        if num > largest:
            largest, larger = num, largest
        elif num > larger:
            larger = num
    return largest, larger

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]

firstLargest, firstLarger  = findLarge(alist[:len(alist)//2])
secondLargest, secondLarger = findLarge(alist[len(alist)//2:])

print sorted((firstLarger, firstLargest, secondLarger, secondLargest))[-2]

#3

If you want an approach that consist in dividing the list, the nearest thing I can think in, is a MergeSort, it works dividing the list in 2, but it sorts a list. Then you can take the last 2 elements.

如果你想要一个包含划分列表的方法，我能想到的最接近的东西是MergeSort，它可以将列表分成2，但它会对列表进行排序。然后你可以采取最后2个元素。

alist = [1, 7, 3, 2, 8, 5, 6, 4]

def find_2_largest(alist):
    sorted_list = mergesort(alist)
    return (sorted_list[-2], sorted_list[-1])    

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

def mergesort(alist):
    if len(alist) < 2:
        return alist
    middle = len(alist) / 2
    left = mergesort(alist[:middle])
    right = mergesort(alist[middle:])
    return merge(left, right)

print find_2_largest(alist)

#4

Try this:

尝试这个：

alist=[10, 0,3,10,90,5,-2,4,18,45,707, 100,1,-266,706, 1]
largest = alist[0]
second_largest = alist[0]
for i in range(len(alist)):
    if alist[i] > second_largest:
        second_largest = alist[i]
    if alist[i] > largest:
        tmp = second_largest
        second_largest = largest
        largest = tmp      

print(largest, second_largest)

#5

O(n) solution

O（n）解决方案

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
m = alist[:2] #m will hold 2 values, fill it with the first two values of alist
for num in alist:
    m = sorted(m + [num],reverse=True)[:2] #appends num to m and sorts it, takes only top 2
m[1] #the second highest element.

EDIT: changed to work with negative numbers. Basic description as follows

编辑：改为使用负数。基本描述如下

First I set m to be the first two elements of alist. As I iterate through alist I will be adding one value to the end of m, then sorting the three elements and throwing away the smallest one. This ensures that at the end m will contain the top two largest elements.

首先，我将m设为alist的前两个元素。当我遍历alist时，我将在m的末尾添加一个值，然后对三个元素进行排序并丢弃最小的元素。这确保了最后m将包含前两个最大的元素。

#6

Without giving away code, I will give you my approach to solving this problem.

在不泄露代码的情况下，我会给你解决这个问题的方法。

1.) Take your list, and sort it from least to greatest. There is a python function to handle this

1.）列出你的清单，并将其从最小到最大排序。有一个python函数来处理这个问题

2.) Split your list into two sections

2.）将您的列表分成两部分

3.) Compare the two sections, take the half with the largest numbers, repeat #2

3.）比较两个部分，取最大数字的一半，重复＃2

4.) When either half contains only two numbers, take the first number from that list

4.）当任何一半只包含两个数字时，从该列表中取出第一个数字

The challenge is you will have to decide what to do if the list cannot be evenly split. Obviously, in the real world, you would sort the list and return the second from last value, but if you must do it by performing a binary split, this is how I would do it :)

挑战是如果列表无法均匀分割，您将不得不决定该怎么做。显然，在现实世界中，您将对列表进行排序并从最后一个值返回第二个值，但如果您必须通过执行二进制拆分来执行此操作，那么我就是这样做的:)

#7

Second largest number in the list:

列表中的第二大数字：

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
second_highest_number = sorted(list(set(alist)))[-2]

If you only want the 2nd largest element in the list (in cases where the highest value may occur twice), just skip the set() and list() call.

如果您只想要列表中的第二大元素（在最高值可能出现两次的情况下），只需跳过set（）和list（）调用即可。

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
second_highest_number = sorted(alist)[-2]

#8

biggest = None
second_biggest = None

biggest = num_list[0]
if num_list[1] > biggest:
   second_biggest = num_list[1]
else:
   second_biggest = biggest
   biggest = num_list [1]

for n in num_list [2:]:
    if n >= biggest:
        biggest, second_biggest = n, biggest
    elif n >= second_biggest:
        second_biggest = n

print second_biggest

#9

I'm amazed that most answers (except by Christian) didn't try to answer OP's real question of finding the solution using divide-and-conquer approach.

我很惊讶大多数答案（除了Christian）并没有试图回答OP使用分而治之的方法找到解决方案的真正问题。

This question is almost identical to this question: Finding the second smallest number from the given list using divide-and-conquer, but it tries to find the least instead of the largest.

这个问题几乎与这个问题相同：使用分而治之的方法从给定列表中找到第二个最小的数字，但它试图找到最小而不是最大的数字。

For which this is my answer:

这是我的答案：

def two_min(arr):
    n = len(arr)
    if n==2:
        if arr[0]<arr[1]:                   # Line 1
            return (arr[0], arr[1])
        else:
            return (arr[1], arr[0])
    (least_left, sec_least_left) = two_min(arr[0:n/2]) # Take the two minimum from the first half
    (least_right, sec_least_right) = two_min(arr[n/2:]) # Take the two minimum from the second half
    if least_left < least_right:            # Line 2
        least = least_left
        if least_right < sec_least_left:    # Line 3
            return (least, least_right)
        else:
            return (least, sec_least_left)
    else:
        least = least_right
        if least_left < sec_least_right:    # Line 4
            return (least, least_left)
        else:
            return (least, sec_least_right)

You can try to understand the code and change it to take the two largest. Basically you divide the array into two parts, then return the two largest numbers from the two parts. Then you compare the four numbers from the two parts, take the largest two, return.

您可以尝试理解代码并将其更改为两个最大的代码。基本上你将数组分成两部分，然后从两部分返回两个最大的数字。然后你比较两个部分中的四个数字，取最大的两个，返回。

This code has a bonus also for limiting the number of comparisons to 3n/2 - 2.

此代码还有一个奖励，用于将比较次数限制为3n / 2 - 2。

#10

alist = [-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
largest = 0
second_largest = 0
for large in alist:
  if second_largest < large:
    second_largest = large

  if largest < large:
    temp = second_largest
    second_largest = largest
    largest = temp

print "First Highest:- %s" %largest
print "Second Highest:- %s" %second_largest

#11

Here is my program, irrespective of complexity

这是我的程序，无论复杂程度如何

if __name__ == '__main__':
    alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
    alist1 = [ ]
    [alist1.append(x) for x in alist if x not in alist1]
    alist1.sort()
    print alist1[-2]