Python 如何在列表中找到第二大数字？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19697504/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to find second largest number in a list?
提问by Manu Lakaster
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)
回答by inspectorG4dget
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
回答by samrap
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
2.) Split your list into two sections
3.) Compare the two sections, take the half with the largest numbers, repeat #2
4.) When either half contains only two numbers, take the first number from that list
1.) 拿出你的清单，从最小到最大排序。有一个 python 函数来处理这个
2.) 将您的列表分成两部分
3.) 比较两部分，取最大数字的一半，重复#2
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 :)
挑战在于，如果列表不能平均分配，您将不得不决定该怎么做。显然，在现实世界中，您将对列表进行排序并从最后一个值中返回第二个值，但是如果您必须通过执行二进制拆分来执行此操作，那么我将这样做:)
回答by placeybordeaux
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 将包含前两个最大的元素。
回答by Christian
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)
回答by thefourtheye
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 (largervariable stores that in the code). If the current number is greater than the largest, current number becomes the largest, largestbecomes just larger.
跟踪最大的数字和第二大的数字（larger变量将其存储在代码中）。如果当前数大于largest，则当前数变为largest，largest变为刚好larger。
largest, larger = num, largestis a shortcut for
largest, larger = num, largest是捷径
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]
回答by Christian
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 sortsa 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)
回答by tacaswell
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
回答by justhalf
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-conquerapproach.
我很惊讶大多数答案（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。
回答by Gaurav Keswani
Second largest numberin 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 elementin 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]
回答by Rohan Chavan
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
