Je me demandais, étant donné une liste d'entiers, disons Actuellement, je suis capable de trouver ce que je crois, c'est (à peu près) une solution essentiellement, mon idée actuelle est de faire: P> l code>, et si nous sommes autorisés à sélectionner 3 entiers dans cette liste, disons gauche code>, code>, droite code>, où milieu> gauche, droite, droite code> et gauche, milieu, droit code> apparaît dans cet ordre dans la liste (c.-à-d. index (gauche) O (n) code> pour rechercher le maximum de Milieu - à gauche + Middle - Droite Code>? Vous pouvez supposer que les listes qui ne satisfont pas ces conditions n'apparaissent pas (par exemple, [5, 0, 5] comme indiqué par Eric Duminil) O (n ^ 2) code> (corrigez-moi si je me trompe). p> maximum = 0
for idx in range(1, N - 1):
left = min(l[0: idx])
right = min(l[idx + 1:])
middle = l[idx]
if left < middle and right < middle:
new_max = middle - left + middle - right
maximum = max(new_max, maximum)
6 Réponses :
Vous êtes définitivement sur la bonne voie, il vous suffit de vous débarrasser de ces opérations min. Donc, mon indice pour vous est que vous puissiez les pré-calculer (en temps linéaire) à l'avance, puis recherchez le min de la boucle, comme vous le faites déjà.
Pour clarifier: vous devez pré-calculer Le défi consiste maintenant à calculer min (liste [0: i]) et min (liste [I: n]) pour tous les i 's, avant la partie que vous avez déjà. L'idée est de les stocker dans deux tableaux, disons m1 et m2 , tel que m1 [i] = min (liste [0: i]) et m2 [i] = min (liste [I: N]) . Ensuite, utilisez m1 et m2 dans votre boucle
m1 et m2 dans le temps linéaire, ce qui signifie que vous n'êtes pas autorisé à utiliser la fonction min pour calculer eux. Si vous avez M1 [i] , comment pouvez-vous calculer m1 [i + 1] à l'aide de la liste [i + 1] ?
Hmm im pas trop sûr de ce que cela signifie exactement ... pourriez-vous clarifier? Surtout la partie du "pré-calcul du minimum" puisque les changements minimaux en fonction du nombre actuel que nous inscrivons et "lève les yeux sur la boucle", que je ne suis pas trop sûr de ce que cela signifie. Merci!
En ce qui concerne la modification: Toutefois, si nous préparons le minimum, cela ne tiendrait-il pas à O (N ^ 2) temps? comme nous devons faire ierrer tout ce que je (O (n)) et ensuite faire la fonction minimale (O (n)) pour une complexité totale du temps de O (N ^ 2)
@Russellng oui. Le défi consiste à le faire en temps linéaire sans utiliser la fonction intégrée min . Si vous avez M1 [i] , comment pouvez-vous calculer m1 [i + 1] ?
Vous pouvez parcourir vos numéros une fois, en gardant un exécutant une valeur minimale et de le stocker à chaque étape, de sorte qu'à la fin, vous savez quelle est la valeur minimale à gauche de chaque index.
C'est O (n).
De même, vous pouvez parcourir tous vos numéros une fois de droite à gauche et déterminer quelle est la valeur minimale à droite de chaque index. C'est o (n).
Ensuite, vous pouvez passer à travers chaque possible O (n) + O (n) + O (n) = O (n). Moyen et prendre le gauche et droit à partir de vos calculs antérieurs. C'est o (n).
L'astuce est que la valeur minimale de la liste est toujours la partie de la solution ( gauche ou droite ).
Oh je vois ... Je ne me suis pas réalisé que le minimum mondial de la liste doit être dans la solution (Facepalm), merci de le pointer!
@ Ericduminil Cependant, l'élément central de (gauche, moyen, droit) est toujours supérieur à celui des deux autres (c'est-à-dire 5 0 5 n'est pas une séquence valide, Lemme vient de modifier cela dans la question initiale pour le rendre plus clair)
Salut, je viens de penser à cela, mais de quoi il y a plusieurs valeurs du minimum? Par exemple. [10, 20, 10, 30, 10]
@Russellng Eh bien, il y a plusieurs solutions. Ici c'est {10 (1), 30, 10 (3)}; et {10 (2), 30, 10 (3)}. Vous pouvez commencer par une valeur minimale arbitraire et trouver toujours l'une des solutions.
Prendre le maximum X-Y ne produit pas nécessairement une solution optimale. Par exemple, avec une entrée de [1, 1000, 0, 1000000, 999999] , la solution optimale est 0, 1000000, 999999 , mais la prise du maximum xy produirait 1, 1000, 0 .
@ user2357112 (1, 1000, 0) est l'optimum calculé à l'étape 2; Alors que (0, 1000000, 999999) est l'optimum à l'étape 3. Nous prenons maintenant le meilleur de deux à l'étape 4, de sorte que l'algorithme est parfaitement correct.
@Matt: Vous décrivez l'algorithme comme prenant le maximum X-Y, et non le maximum de la valeur que nous essayons d'optimiser. Même si vous prenez le maximum de la valeur, nous essayons d'optimiser à l'étape 4, [999999, 1000000, 1, 1000, 0] trouve 1, 1000 à l'étape 2 Et rien à l'étape 3, l'étape 4 prend donc 1, 1000, 0 au lieu de 999999, 1000000, 0 .
@ user2357112 1) max (x-y) donne la même paire x, Y, en tant que max (2x-y-global_min_min), cela devrait être évident; 2) il fait, car nous vérifions des index qui sont supérieurs à l'indice d'élément zéro (min); Essayez de relire attentivement les deux conditions.
@Matt: Non, ça ne le fait pas. Max (x-y) donne moins de poids à x que max (2x-y-global_min).
De plus, vous n'avez pas décrit comment prendre le maximum x-y en temps linéaire.
@ user2357112 1) il donne les mêmes éléments x, y, z; Si vous avez besoin de la valeur de Max (2x-Y-Z), vous devez le calculer par la suite; d'ailleurs. calculer une expression plus courte dans la boucle est toujours une bonne idée; 2) Ceci est trivial, n'est-ce pas?
La valeur maximale XY dans les [999999, 0] L'exemple est de 999, de la prise de X = 1000 et Y = 1, mais la valeur maximale 2x-y-global_min provient de la prise de la prise. x = 1000000 et Y = 999999, même si cela donne xy = 1.
@ user2357112 nah, j'étais trop négligeable et, probablement, sommeil. OK, max (2x-y) dans les deux cas.
Voici un moyen de calculer les minimums, à gauche et à droite de chaque index, dans O (n):
11
Bonjour, pourrais-je préciser quelle est l'utilisation du flotteur ("INF")? Merci!
@Russellng: Cela signifie Infinity . Il est utilisé comme point de départ pour la première comparaison minimale. Tout nombre est plus petit que float ("INF")
solution possible: sortie:
Hmm pour cela, pourrait-il exister une erreur? En ce qui concerne la liste des exemples donnés, la somme maximale doit être de 155 (en sélectionnant 13, 85, 2).
Voici quelques horaires! N'hésitez pas à éditer le code qui fait le chronométrage et \ Ajouter de nouvelles entrées.
maximum = max(2*z -sum(x) for x, z in zip([[min(lst[:i+1]), min(lst[i+2:])] for i, _ in enumerate(lst[:-2])], lst[1:-1]))
Pas vraiment sûr, mais pour moi, cela ressemble à un O (n).
Pourquoi ne prenez-vous pas simplement le plus grand Middle et le plus petit
gauche etdroit ?Essayez 3 Différent
Liste S avec chacun deux fois plus grand que le précédent et l'heure. Vous serez capable de voir si elle (n) ou o (n ^ 2)@Mathieu, mais je pensais que les fonctions min et max sont O (n) heure?
@Ev. Kounis ok je vais aller faire maintenant et mettre à jour
@khelwood oh whoops j'ai oublié d'ajouter quelque chose de désolé mon mauvais! : P
J'ai mis en œuvre une solution pour un problème similaire. Je reviendrai ici la nuit. Marquage préféré
@Crook ah ok merci!
Vous pouvez le faire dans O (n) en définissant des files d'attente qui conservent min et max, comme dans cette question: Stackoverflow.com/questions/ 4802038 / ...
Oui mon mauvais. Je le lis trop vite.
@MiriamFarber Merci, bien que l'explication indiquée sur cette page soit un peu déroutante ... mais j'essaierai de lire à nouveau et de comprendre :)