Compte tenu d'une matrice triée, je veux obtenir le plus petit élément qui est égal ou moins de moins que la touche transcédente
J'ai déjà essayé de trouver un écart entre chaque élément et renvoyer celui avec le moins d'espace, mais cela ne donne pas le message souhaité résultat car il renvoie également la valeur plus grande, alors le code p>
sorted_li= [25,22,15,14,12,6,4]
def find_nearest_small_value(key,sorted_li):
gap_current, gap_global, value = 0, key, sorted_li[0]
for i in sorted_li:
gap_current = abs(i-key)
if gap_global>=gap_current:
gap_global=gap_current
value=i
return value
3 Réponses :
traverser chaque élément de la liste triée donnée et renvoyez l'élément lorsque la condition est remplie. La complexité de cas pire est Couper l'espace de recherche en deux Chaque fois que nous comparons et rendant ainsi l'algorithme plus efficace. La complexité est O (n) . approche effantients: Recherche binaire
O (journal n) .
Oui cela fonctionne .Bien que j'aurais dû mentionner la possibilité de la liste non formée
Votre pour boucle fera exactement 1 (une) itération dans le cas réussi ou une boucle inutile jusqu'à la fin si toutes les valeurs sont supérieures à la touche .
Oui, j'ai également supposé que la liste triée donnée est triée en ordre décroissant (le plus important au plus petit). Vous pouvez toujours utiliser le trié (liste, inverse = true) sur la liste en premier si la liste est non traitée. Cependant, cela augmentera la complexité de temps de l'algorithme.
Pourquoi quelqu'un aurait-il besoin d'une boucle pour cela ?? Renvoyer le premier élément comme le plus petit, s'il est inférieur à la touche ou Répondre à la question ci-dessous : Aucun sinon:
Comment êtes-vous supposé vérifier chaque élément sans les vérifier
@Abhay Dans le tableau trié, le plus petit élément est le premier, pourquoi dois-je vérifier tous?
Si LI = [22,25,28,39] et je donne une clé = 31 Il retournera 22 bien que la sortie souhaitée soit 28
Peut-être que je devrais poser ma question comme retournez le plus grand élément inférieur ou égal à la clé donnée dans une liste
@Abhay Voir la modification, tout fonctionne comme c'est censé.
Ceci fonctionnera pour les séquences d'entrée triées et non formées: Il est très facilement lisible et une solution simple
Ceci est O (n), comparé aux solutions qui incluent le tri (qui est O (nlogn)))
Très vrai. Bien que ce soit une option. C'est probablement pas la meilleure option
Ah bon? Je pensais que o (nlogn)) pourrait être plus rapide dans certains cas ici par rapport à O (n) ou je me trompe?
Je ne sais pas si vous pouvez trouver la valeur de n pour faire o (n)> o (nlogn) =)
On dirait que vous utilisez le mauvais calcul "gap" alors ...
Ce code renvoie toujours 4 ... Voulez-vous dire
Valeur de retour ?@ cricket_007 oui u r droit bien que c'était un typo, il ne renvoie toujours pas la sortie souhaitée
Je ne sais pas pourquoi vous pensez que vous devez calculer des lacunes. Vous pouvez retourner l'élément qui est immédiatement inférieur ou égal à la clé tout en itération
@ cricket_007 oui merci pour l'aperçu. Bien que cela ne fonctionne pas si la liste n'est pas triée déjà
Vous avez littéralement dit donné un tableau trié . Si vous avez un tableau non formé, alors une question distincte
Même si c'était non traduit, n'êtes-vous pas autorisé à trier?
Je pense que vous avez peut-être formé votre question à tort. Je crois que vous vouliez demander: donné une matrice triée, trouvez l'élément plus important qui est égal ou inférieur à la clé transmise?
@Garygoh oui! ça va faire.