Min et Max d'une Liste en Python (sans l'aide de min/max fonction)

Je me demandais si il existe un moyen de trouver des min & max d'une liste sans l'aide de min/max des fonctions en Python. J'ai donc écrit un petit code pour la même utilisation de la récursivité. Ma logique est très naïve: je fais deux piles (min_stack et max_stack) qui permettent de garder une trace de minimum et de maximum lors de chaque appel récursif. J'ai deux questions:

  1. Quelqu'un pourrait m'aider à estimer la complexité de mon code?
  2. Est-il une meilleure façon de le faire? Permettra de tri de la liste à l'aide de mergesort/quicksort et ramasser premier et le dernier élément de donner un meilleur rendement?

Merci

Voici ma tentative en 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()
  • wow... Qui semble vraiment trop complexe ...
  • Je suppose à l'aide de tri et de prendre le 0 et -1 index sera plus rapide ... et beaucoup plus lisible a = sorted(my_list);min,max=a[0],a[-1]; Si j'étais un interviewer et posé cette question ... la canidate qui a remis ce que vous avez ne serait pas faire le travail...
  • ouais...c'est assez complexe car on m'a demandé de la mettre en œuvre à l'aide de Meules comme un moyen de faire de l'exercice.
  • ahh si vous avez été explicitement demandé d'utiliser des piles alors peut-être ... (bien que je ne sais pas pourquoi quelqu'un voudrait que ...)
  • Je ne suis pas sûr si le tri est le meilleur moyen pour ce faire. Mais merci pour le commentaire.