Python 中列表的最小值和最大值（不使用 min/max 函数）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15148491/
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
Min and Max of a List in Python (without using min/max function)
提问by Prakhar Mehrotra
I was wondering if there is a way to find min & max of a list without using min/max functions in Python. So i wrote a small code for the same using recursion. My logic is very naive: I make two stacks (min_stack and max_stack) which keep track of minimum and maximum during each recursive call. I have two questions:
我想知道是否有一种方法可以在不使用 Python 中的 min/max 函数的情况下找到列表的最小值和最大值。所以我使用递归编写了一个小代码。我的逻辑非常天真：我制作了两个堆栈（min_stack 和 max_stack），它们在每次递归调用期间跟踪最小值和最大值。我有两个问题：
- Could somebody help me estimate the complexity of my code?
- Is there a better way to do this? Will sorting the list using mergesort/quicksort and picking up first and last element give a better performance?
- 有人可以帮我估计我的代码的复杂性吗？
- 有一个更好的方法吗？使用合并排序/快速排序对列表进行排序并选取第一个和最后一个元素会带来更好的性能吗？
Thank you
谢谢
Here is my attempt in Python:
这是我在 Python 中的尝试：
minimum = []
maximum = []
# Defining Stack Class
class Stack:
def __init__(self) :
self.items = []
def push(self, item) :
self.items.append(item)
def pop(self) :
return self.items.pop()
def access(self, index):
return self.items[index]
def isEmpty(self) :
return (self.items == [])
def length(self):
return len(self.items)
def minmax(input_list):
# make two stacks, one for min and one for max
min_stack = Stack()
max_stack = Stack()
# comparing the first two elements of the list and putting them in appropriate stack
if input_list[0]<input_list[1]:
min_stack.push(input_list[0])
max_stack.push(input_list[1])
else:
max_stack.push(input_list[0])
min_stack.push(input_list[1])
# Pushing remaining elements of the list into appropriate stacks.
for i in range(2, len(input_list)):
if input_list[i] < min_stack.access(-1):
min_stack.push(input_list[i])
else:
max_stack.push(input_list[i])
# to find minimum
minlist = []
while min_stack.length() > 0:
minlist.append(min_stack.pop())
# to find maximum
maxlist = []
while max_stack.length() > 0:
maxlist.append(max_stack.pop())
if len(minlist) > 1:
minmax(minlist)
else:
minimum.append(minlist)
if len(maxlist) > 1:
minmax(maxlist)
else:
maximum.append(maxlist)
def main():
input_list = [2, 0, 2, 7, 5, -1, -2]
print 'Input List is: ', input_list
minmax(input_list)
print 'Global Minimum is: ', minimum[0]
print 'Global Maximum is: ', maximum[len(maximum)-1]
if __name__ == "__main__":
main()
回答by Simon
Using sorted()would, of course, be reliable, quick to write, and high performance for moderate-sized lists because it is built-in. For large lists, an O(n) algorithm would be faster e.g.:
使用sorted()当然会，因为它是内置的中等规模名单是可靠的，快速的写入和高性能。对于大型列表，O(n) 算法会更快，例如：
def minmax1 (x):
# this function fails if the list length is 0
minimum = maximum = x[0]
for i in x[1:]:
if i < minimum:
minimum = i
else:
if i > maximum: maximum = i
return (minimum,maximum)
print(minmax1([9,8,7,6,5,4,3,2,1,11,12,13,14,15,16,17,18,19]))
print(minmax1([1]))
print(minmax1([2, 0, 2, 7, 5, -1, -2]))
... for which the output is:
...输出为：
(1, 19)
(1, 1)
(-2, 7)
I was interested to check the performance of the two alternatives. On my PC running Windows XP and Python 3.2.3, I found that the sorting approach is faster than the minmax1()function defined above for lists of fewer than 500 elements but, for longer lists, the O(n) minmax1()is faster. My timing test code was as follows:
我有兴趣检查这两种替代方案的性能。在我运行 Windows XP 和 Python 3.2.3 的 PC 上，我发现排序方法比minmax1()上面为少于 500 个元素的列表定义的函数更快，但对于更长的列表，O(n)minmax1()更快。我的时序测试代码如下：
def minmax_sort(x):
x = sorted(x)
return (x[0],x[-1])
import timeit
aa = list(range(0,100))
a = aa
while (1):
stime = min(timeit.repeat('minmax_sort(a)', "from __main__ import minmax_sort,a",number=1000))
mtime = min(timeit.repeat('minmax1(a)', "from __main__ import minmax,a",number=1000))
if (stime > mtime):
break
else:
a = a + aa
print(len(a))
回答by KingKong BigBong
Finding Min and Max of a list using only recursion.
仅使用递归查找列表的最小值和最大值。
I had this similar assignment last week and I divided the code into three parts.
上周我有一个类似的任务，我把代码分成了三个部分。
Step 1: Finding the minimum value in list
第 1 步：查找列表中的最小值
def RecursiveMin(L):
if len(L)==2:
if L[0]<L[1]:
return L[0]
else:
return L[1]
else:
X= RecursiveMin(L[1:])
if L[0]<X:
return L[0]
else:
return X
Step 2: Sorting the list using into ascending order (smallest to largest)
第 2 步：使用升序对列表进行排序（从最小到最大）
def Sort(x):
L=sorted(x)
if x==L:
return x
else:
i=0
for i in range (len(x)):
if x[i] > x[i+1] :
break
unsortedPart = x[i:]
R = RecursiveMin(unsortedPart)
I = unsortedPart.index(R)
for j in range (len(x)):
if x[j] > R :
del x[(I+i)]
x.insert(j,R)
break
return Sort(x)
(I have previously answered a sorting a list question and provided the same code. So please don't flag me for plagiarism since it's my own code Likn: Finding minimum element in a list (recursively) - Python).
（我之前回答了一个排序列表问题并提供了相同的代码。所以请不要标记我抄袭，因为它是我自己的代码 Likn: Finding minimum element in a list (recursively) - Python）。
**Step 3: Make a new function with an argument whether the user wants Min value or Max*
**第 3 步：创建一个带参数的新函数，无论用户想要最小值还是最大值*
def minMax(lst,user):
if user == min:
return Sort(lst)
elif user == max:
s = Sort(lst)
return s[::-1]
The last step is not recursive but if you compile all the three steps into one function it will be "1 recursive function". P.S if your question was only about finding the Min and Max in a list you can skip Step 2and make a few changes to to Step 1and Step 3
最后一步不是递归的，但如果将所有三个步骤编译为一个函数，它将是“1 个递归函数”。PS 如果您的问题只是关于在列表中查找最小值和最大值，您可以跳过步骤 2并对步骤 1和步骤 3进行一些更改
回答by Jameson Welch
If you use the sorted() function, just call the first index for minimum and the last index for maximum. No need for a for loop.
如果您使用 sorted() 函数，只需调用第一个索引为最小值，最后一个索引为最大值。不需要 for 循环。
def minimum(x):
x = sorted(x)
return x[0]
def maximum(x):
x = sorted(x)
return x[-1]
print(minimum([2, -5, 79, 20, -67])
print(maximum([45, -78, 950, 39, -567])
The output is:
输出是：
-67
950
回答by Rishav Bhurtel
This would be very simple and easy to understand. Hope this will help you.
这将非常简单且易于理解。希望这会帮助你。
arr = []
num = int(input("Enter number of elements in list: "))
for i in range(0, num):
ele = int(input("Enter elements: "))
arr.append(ele)
min = arr[ 0 ]
for a in arr:
if a < min:
min = a
print ("The minimum number in the list is: ", min)
max = arr[0]
for a in arr:
if a > max:
max = a
print("The maximum number in the lit is: ", max)
回答by cdlane
I was asked to implement it using Stacks as a way of exercise.
我被要求使用 Stacks 作为一种练习来实现它。
I'm surprised several of the solutions require multiple passesthrough the list to determine the minimum and maximum. Here's a simple Python 3 recursive solution, using stacksper the OP, that only makes one pass through the list:
我很惊讶一些解决方案需要多次通过列表来确定最小值和最大值。这是一个简单的 Python 3 递归解决方案，每个 OP使用堆栈，它只通过列表：
def minmax(array, minimum=None, maximum=None):
head, *tail = array
if minimum is None:
minimum = [head]
elif head < minimum[-1]:
minimum.append(head)
if maximum is None:
maximum = [head]
elif head > maximum[-1]:
maximum.append(head)
if tail:
return minmax(tail, minimum, maximum)
return minimum.pop(), maximum.pop()
if __name__ == "__main__":
array = [2, 0, 2, 7, 5, -1, -2]
minimum, maximum = minmax(array)
print(array, minimum, maximum)
array = [13]
minimum, maximum = minmax(array)
print(array, minimum, maximum)
array = [9, 8, 7, 6, 5, 4, 3, 2, 1, 11, 12, 13, 14, 15, 16, 17, 18, 19]
minimum, maximum = minmax(array)
print(array, minimum, maximum)
Though the stacks aren't strickly necessary for this code to work.
尽管堆栈对于此代码的工作并不是绝对必要的。
