不使用min/max函数求列表的最小值和最大值

Question

我在想有没有办法在Python中找到一个列表的最小值和最大值，而不使用min和max这两个函数。于是我写了一段小代码来实现这个功能，使用了递归。我的思路很简单：我创建了两个栈（min_stack和max_stack），在每次递归调用时用它们来记录当前的最小值和最大值。我有两个问题：

1. 有没有人能帮我估算一下我这段代码的复杂度？
2. 有没有更好的方法来实现这个？如果用归并排序或快速排序对列表进行排序，然后取第一个和最后一个元素，性能会更好吗？

这是我在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()

Answer 1

我被要求用栈来实现这个功能，作为一种练习。

我很惊讶，有几个解决方案需要对列表进行多次遍历才能找出最小值和最大值。这里有一个简单的 Python 3 递归解决方案，按照提问者的要求，使用了栈，只需对列表进行一次遍历：

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)

不过，这段代码并不一定非要用栈才能工作。

Answer 2

仅使用递归找到列表中的最小值和最大值

我上周有一个类似的作业，我把代码分成了三个部分。

第一步：找到列表中的最小值

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

第二步：将列表按从小到大的顺序排序

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)

（我之前回答过一个关于排序列表的问题，并提供了相同的代码。所以请不要因为这是我自己的代码而举报我抄袭。链接：递归找到列表中的最小元素 - Python）。

*第三步：创建一个新函数，参数决定用户想要最小值还是最大值

def minMax(lst,user):
    if user == min:
       return Sort(lst)
    elif user == max:
       s = Sort(lst)
       return s[::-1]

最后一步不是递归的，但如果你把这三步合并成一个函数，它就会变成“一个递归函数”。
附注：如果你的问题只是关于在列表中找到最小值和最大值，你可以跳过第二步，并对第一步和第三步做一些小改动。

Answer 3

使用 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]))

... 这个的输出是：

(1, 19)
(1, 1)
(-2, 7)

我想看看这两种方法的性能。在我运行 Windows XP 和 Python 3.2.3 的电脑上，我发现对于少于 500 个元素的列表，排序的方法比上面定义的 minmax1() 函数要快，但对于更长的列表，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))