4
Étant donné deux tableaux triés, A et B, trouvez i, j pour lequel | A [i] - B [j] | est minimum.Trouver la différence minimale entre deux tableaux
A
Répondre
8
Comme les tableaux sont triés, vous pouvez les traverser avec 2 pointeurs (un pour chaque tableau). Si |A[i+1] - B[j]| < |A[i] - B[j+1]| alors incrémenter i, sinon incrémenter j. Continuez jusqu'à ce que vous ayez atteint la fin de l'un des tableaux. Gardez une trace des indices minimaux au fur et à mesure.
+0
Quelle est la complexité de l'exécution de ce code dans le pire des cas? Ça devrait être n^2, non? – Yashasvi
+0
O (nlogm): pour chaque élément dans A, utilisez la méthode de recherche binaire pour trouver l'élément avec la valeur la plus proche dans le tableau B. – Yashasvi
+0
Comment puis-je trouver des réponses comme moi? Quelle était la méthode que vous avez utilisée pour le résoudre? –
Questions connexes
- 1. Algorithme pour trouver la différence entre deux tableaux
- 2. Comment trouver la différence entre deux chaînes?
- 3. Comment trouver la différence entre deux dates en oracle?
- 4. Obtenez la différence réelle entre deux tableaux en php
- 5. comment trouver la distance entre les éléments de deux tableaux?
- 6. Trouver la différence minimale entre chaque élément d'un vecteur et un autre vecteur
- 7. SQL pour trouver la différence entre deux lignes
- 8. Trouver la différence entre le contenu de deux fichiers
- 9. Trouver la différence situé entre deux dictionnaires complexes
- 10. Problème de trouver la différence en jours entre deux dates
- 11. Redimensionnement des tableaux - Différence entre deux blocs d'exécution?
- 12. Différence entre deux cartes
- 13. Trouver la différence entre la liste
- 14. Différence entre deux procédures stockées
- 15. 'Différence' entre deux quaternions
- 16. Classement par la différence entre deux moyennes
- 17. Ruby: quelle est la différence avec ces deux tableaux?
- 18. Perl boucle entre deux tableaux
- 19. Différence entre les listes et les tableaux
- 20. PHP: Comment trouver la différence de tableaux 2D?
- 21. Trouver la différence entre 2 lignes spécifiques
- 22. trouver la différence entre 2 dates
- 23. Comment calculer la différence entre 2 tableaux int en pourcentage
- 24. PHP: différence visuelle entre 2 tableaux
- 25. différence entre ces deux conditions
- 26. Différence entre deux heures d'horloge
- 27. Différence entre deux DateTimes C#?
- 28. Différence entre ces deux syntaxes
- 29. C# - Différence entre deux dates?
- 30. Différence entre deux valeurs d'horodatage SQL
S'il vous plaît, exprimez ce que vous aimeriez savoir comme une question! –
Étant donné 2 questions de devoirs, vous devez ... au moins les essayer vous-même. –
Il veut connaître le moyen le plus efficace pour trouver la plus petite distance entre deux éléments dans les deux tableaux différents. – sethvargo