2

我想知道是否有一种方法可以在不使用 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()
4

9 回答 9

9

对于中等大小的列表，使用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 的 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))
于 2013-03-01T04:59:16.570 回答
3

仅使用递归查找列表的最小值和最大值。

上周我有类似的任务，我将代码分为三个部分。

第 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

第 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)

（我之前回答了一个排序列表问题并提供了相同的代码。所以请不要标记我抄袭，因为这是我自己的代码 Likn：Finding minimum element in a list (recursive) - Python）。

**步骤 3：使用参数创建一个新函数，无论用户想要最小值还是最大值*

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

最后一步不是递归的，但如果您将所有三个步骤编译成一个函数，它将是“1 个递归函数”。PS如果您的问题只是关于在列表中查找最小值和最大值，您可以跳过第 2步并对第 1 步和第 3步进行一些更改

于 2018-03-05T06:07:33.940 回答
1

为了找到最大值，我们可以使用以下逻辑：

def mx(y):
    max_n = y[0] # initial the max to the first element

for i in range(len(y)-1): # for every element check if its greater than max.
    if y[i+1]>max_n:
        max_n = y[i+1] # if so, assign max to the value
return(max_n)
于 2021-03-22T00:26:03.493 回答
1

这将非常简单易懂。希望这会帮助你。

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)
于 2019-11-17T05:12:31.103 回答
1

我被要求使用 Stacks 作为一种锻炼方式来实现它。

我很惊讶有几个解决方案需要多次遍历列表来确定最小值和最大值。这是一个简单的 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)

尽管堆栈对于此代码的工作并不是绝对必要的。

于 2019-11-17T05:43:11.343 回答
0

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

输出是：

-67
950
于 2019-06-29T17:39:44.250 回答
0 
def inIntervalle(liste, min, max):
    liste_intervalle = []
    for i in range(len(liste)):
        if liste[i] < max and liste[i] > min:
            liste_intervalle.append(liste[i])
    return liste_intervalle
于 2020-12-22T01:53:45.690 回答
0

这是一个使用递归函数的简单解决方案。让arr成为您的数字列表。可以通过到达列表末尾并一次比较最后 2 个数字并将结果传播回前一个函数调用，一直到第一个元素，可以找到最小值/最大值。

def get_min_max(arr):
    min = find_peak(arr, peak = "minimum")
    max = find_peak(arr, peak = "maximum")
    return {"minimum": min, "maximum": max}

def find_peak(arr, peak):
    if len(arr) == 1: # base condition
        return arr[0]    
    n1 = arr[0]
    n2 = find_peak(arr[1:], peak) # first element removed for each call
    if peak == "maximum":
        if n1 > n2: 
            return n1
        else:
            return n2
    else:
        if n1 < n2: 
            return n1
        else:
            return n2
于 2022-01-05T07:40:44.723 回答
-1 
min=99999999999999
while True:
    value=int(input('enter your values:'))
    if value==333: #enter 333 to end the input
        break
    if min>value:
        min=value
print(min)
于 2021-11-11T11:01:38.890 回答