Je me débats avec une tâche assez facile qui a une gamme d'entiers non négatifs où je dois retourner la distance la plus proche.
Array: solution: SORS , Je n'ai réussi à écrire qu'une solution O (n ^ 2), qui n'est évidemment pas suffisamment bonne: aucune idée sur la manière d'améliorer cela? arr = [8, 24, 3, 20, 1 , 17] 2 , arr [2] -ron [4]
3 Réponses :
La solution consiste à trier la matrice, puis à le savoir. Vous n'avez maintenant besoin que de vérifier les candidats adjacents Ceci fonctionne dans Notez qu'il s'agit d'une généralisation de Problème de distinction de l'élément , donc si vous êtes intéressé par le pire des performances, vous ne pouvez pas mieux que (arr [i], arr [i + 1]) , et non toutes les paires d'éléments.
O (nlogn) .
O (nlogn) .
Pourriez-vous vérifier ma question mise à jour? Nlogn est juste bien.
@Cojones me semble correcte, mais je ne connais pas vraiment la syntaxe de rubis. L'algorithme semble correct, aucune idée si je manque des problèmes de rubis spécifiques ou non.
@ Cojones En outre, si votre question mise à jour est venue de ma réponse, vous devriez mieux l'écrire également dans les réponses, afin que les gens comprennent le contexte de la réponse (qui est venu avant la modification de la question et que la modification était basée sur elle. ).
La syntaxe va bien, merci beaucoup! Alors devrais-je répondre à ma propre question ou modifier votre réponse?
Suscitais spécialement parce que l'explication sur la complexité inférieure liée :)
La solution que AMIT posté est correctement n * journal (n) heure, qui est le plus rapide que la quantité de temps qu'une solution pourrait être trouvée. Le code Ruby pour sa solution examinera quelque chose sur les lignes de ceci:
Généralement pour ce problème associé à un matrice. Si vous avez un algorithme égal ou pire que O (n ^ 2), vous pouvez toujours envisager d'utiliser l'algorithme de tri pour le traiter. Prend habituellement O (LGN), alors vous pouvez avoir un algorithme linéaire après cela.
Pour ce problème, vous pouvez trier ce tableau. Ensuite, comparez simplement des éléments adjacents pour une boucle. La complexité du temps de résultat final est O (n logn) qui est meilleure que votre idée d'origine.
afin que vous puissiez: puis utilisez une boucle pour Copmare