所以我必须从列表中找到第二大的数字。我通过简单的循环来做到这一点。
我的方法是将一个列表分成两部分，然后找到最大的数字分成两部分，然后比较两个数字。我将从其中两个中选择较小的数字。我不能使用现成的功能或不同的方法。
基本上，这是我的代码。但它不能正确运行
#!/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)
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) 算法：
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
如果您想要一种包括划分列表的方法，我能想到的最接近的方法是 MergeSort，它可以将列表划分为 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)
您不必对输入进行排序，并且此解决方案在 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
输出
100
跟踪最大数字和第二大数字（larger变量存储在代码中）。如果当前数大于largest，则当前数变为largest，largest变为just larger。
largest, larger = num, largest是一个捷径
temp = largest
largest = num
larger = temp
编辑：根据评论中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]
尝试这个：
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)
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.
编辑：改为使用负数。基本说明如下
首先，我将 m 设置为 alist 的前两个元素。当我遍历 alist 时，我将在 m 的末尾添加一个值，然后对三个元素进行排序并丢弃最小的一个。这确保了最后 m 将包含前两个最大的元素。
在不泄露代码的情况下，我将为您提供解决此问题的方法。
1.) 拿出你的清单，从小到大排序。有一个python函数来处理这个
2.) 将您的列表分成两部分
3.）比较两个部分，取最大数字的一半，重复#2
4.）当任何一半只包含两个数字时，从该列表中取出第一个数字
挑战在于，如果列表不能平均分配，您将不得不决定该怎么做。显然，在现实世界中，您将对列表进行排序并返回倒数第二个值，但如果您必须通过执行二进制拆分来做到这一点，我会这样做:)
列表中第二大的数字：
alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
second_highest_number = sorted(list(set(alist)))[-2]
如果您只想要列表中的第二大元素（在最高值可能出现两次的情况下），只需跳过 set() 和 list() 调用。
alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
second_highest_number = sorted(alist)[-2]
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
我很惊讶大多数答案（Christian 除外）并没有尝试回答 OP 的真正问题，即使用分而治之的方法找到解决方案。
这个问题几乎与这个问题相同：Finding the second minimum number from the given list using divide-and-conquer，但它试图找到最小的而不是最大的。
这是我的答案：
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)
您可以尝试理解代码并将其更改为取最大的两个。基本上，您将数组分成两部分，然后从两部分中返回两个最大的数字。然后你比较这两个部分的四个数字，取最大的两个，返回。
此代码还具有将比较次数限制为3n/2 - 2.
alist=[10, 0,3,10,90,5,-2,4,18,45,707, 100,1,-266,706, 1]
print(max(alist))
second_largest=alist[0]
for i in range(len(alist)):
if (alist[i]>second_largest and alist[i]!=max(alist)):
second_largest=alist[i]
print(second_largest)
list1=[1,10,2,3,5,7,1,-32,90,99,99]
max=0
secmax=0
for i in list1:
if i>max:
max=i
for i in list1:
if i>secmax and max!=i:
secmax=i
print(secmax)
alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
sorted_list = sorted(set(alist))
sorted_list.pop()
print(max(sorted_list))
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
这是我的程序，无论复杂性如何
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]