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:
- Quelqu'un pourrait m'aider à estimer la complexité de mon code?
- 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.
Vous devez vous connecter pour publier un commentaire.
À l'aide de
sorted()
serait, bien sûr, être fiable, rapide à écrire, et de haute performance, de taille modérée listes dans la mesure où il est intégré. Pour les grandes listes, un algorithme O(n) serait plus rapide par exemple:... pour lequel la sortie est:
Je me suis intéressé à vérifier les performances de ces deux alternatives. Sur mon PC sous Windows XP et Python 3.2.3, j'ai trouvé que l'approche de tri est plus rapide que la
minmax1()
la fonction définie ci-dessus pour les listes de moins de 500 éléments, mais, pour plus de listes, O(n)minmax1()
est plus rapide. Mon calendrier de code de test a été comme suit:return min(x),max(x)
commence à être la méthode la plus rapide sur les listes de 300 éléments ou plus avec votre exemple des listes et des listes aléatoires.Trouver Min et Max d'une liste en utilisant seulement la récursivité.
J'ai eu cette fonction similaire la semaine dernière et j'ai divisé le code en trois parties.
(J'ai déjà répondu à un tri d'une liste de question et a fourni le même code. Donc merci de ne pas le drapeau de moi pour plagiat puisque c'est mon propre code
Likn: Trouver minimale de l'élément dans une liste (de manière récursive) - Python ).
La dernière étape n'est pas récursive, mais si vous compilez tous les trois étapes en une fonction, il sera "1 fonction récursive".
P. S si votre question était seulement de trouver le Min et Max dans une liste que vous pouvez passer Étape 2 et de faire quelques modifications à Étape 1 et Étape 3
Si vous utilisez le tri() de la fonction, il suffit d'appeler le premier indice pour le minimum et le dernier indice pour le maximum. Pas besoin d'une boucle for.
La sortie est: