Déterminer si oui ou non il existe deux éléments d'un Ensemble dont la somme est exactement x - solution correcte?
Prises à partir d'Introduction aux Algorithmes
Décrire Θ(n lg n) en temps de l'algorithme
qui, étant donné un ensemble S de n entiers et
d'un autre nombre entier x, détermine si
ou pas, il existe deux éléments de S
dont la somme est exactement x.
C'est ma meilleure solution implémentée en Java jusqu'à présent:
public static boolean test(int[] a, int val) {
mergeSort(a);
for (int i = 0; i < a.length - 1; ++i) {
int diff = (val >= a[i]) ? val - a[i] : a[i] - val;
if (Arrays.binarySearch(a, i, a.length, diff) >= 0) {
return true;
}
}
return false;
}
Maintenant ma 1ère question est: Est-ce une bonne solution? De ma compréhension, mergeSort doit effectuer le tri en O(n lg n), la boucle doit prendre en O(n lg n) (n de l'itération est multiplié par O(lg n) pour la recherche binaire, résultant en O(2n lg n), de sorte qu'il devrait être correct.
Ma 2ème question est: y at-il de meilleures solutions? Est tri la matrice essentielle?
- Êtes-vous autorisé à utiliser hachage de jeux? Si oui, alors vous pouvez obtenir de O(n), voir ci-dessous.
(val >= a[i]) ? val - a[i] : a[i] - val
ce queMath.abs()
est pour 🙂- Oui,
Math.abs
est pour ça, mais je dirais même plus: il n'est pas nécessaire ici. En fait, est mauvais.diff
doit toujours être affectées à la valeurval-a[i]
indépendamment de savoir si cette différence est positive ou négative. - comme le suggère quelques réponses ci-dessous il y a une meilleure O(n) sol'n donné un peu d'hypothèses sur l'entrée.
- Oui le tri semble être nécessaire, mais une fois que vous avez une liste triée, vous pouvez améliorer. Au lieu de naïvement à l'aide de binaires de recherche, vous pouvez penser de la méthode suivante: Initialiser les pointeurs l,r de début et de fin de la liste. Vérifier un[l]+a[r] = f; Si f > x, r--; else if f<x, puis l++; else a[l]+a[r]=f=x est votre solution. Bien que la complexité du temps est toujours en O(nlogn) observer que la méthode ci-dessus ne recherche linéaire O(n).
Vous devez vous connecter pour publier un commentaire.
Ta solution me semble bien. Oui, vous avez besoin de trier parce que c'est un pré requis pour une recherche binaire. Vous pouvez apporter une légère modification à votre logique comme suit:
Il y a un autre très rapide de la solution: Imaginez que vous avez à résoudre ce problème en Java pour environ 1 milliard d'entiers. Vous savez qu'en Java entiers aller de
-2**31+1
à+2**31
.Créer un tableau avec
2**32
milliards de bits (500 MO, trivial à faire sur le matériel d'aujourd'hui).Itérer sur votre jeu: si vous avez un entier, définissez bit correspondant est à 1.
O(n) jusqu'à présent.
Itérer une fois de plus sur votre jeu: pour chaque valeur de, vérifier si vous avez un ensemble de bits à "actuel val - x".
Si vous en avez un, vous retourner la valeur true.
Accordé, il a besoin de 500 MO de mémoire.
Mais ce doit courir autour de toute autre O(n log n) solution si vous avez, disons, de résoudre ce problème avec 1 milliard d'entiers.
O(n).
return false;
est 😉n
puis créer un tableau de cette taille et de l'exécution de cet algorithme. C'estO(k)
(où k est la valeur la plus grande), en raison de la mise à zéro de la pile de disques. Des algorithmes tels que ce sont connu comme une pseudo-polynomial (en.wikipedia.org/wiki/Pseudo-polynomial_time), et bien utile dans certains (beaucoup) de cas dans le monde réel, il n'est pas une solution à ce problème quek
est pas lié à lan
.int
un jour sera 64 bits, je vais joyeusement point et se moquer d'eux.C'est correct; votre algorithme va s'exécuter en O(n lg n) fois.
Il y a une meilleure solution: votre logique pour le calcul de la diff est incorrect. Peu importe si
a[i]
est supérieure ou inférieure àval
, vous avez encore besoin de diffval - a[i]
.va - a[i]
.Voici un O(n) solution à l'aide d'un algorithme de hachage-set:
hashCode(i)==i
, mais HashSet n'utilisez pas 2^32 seaux, il utilise moins que cela. Donc, la fonction de hachage utilisée est un module sur le nombre de compartiments. Autant que je sache, la Java HashSet re-hachage stratégie ne garantit pas le pire cas O(1) éléments par seau (sauf dans le sens trivial que presque tout fait sur bornée taille des entiers est O(1)), car il est basé sur le facteur de charge, et non sur l'occupation de la pire seau dans le tableau.O(n)
, parce que la table de Hachage des recherches ne sont pas les pires cas deO(1)
(ce qui signifie qu'ils ne sont pas les pires cas deΘ(1)
), ils sont en moyenne-casΘ(k/n)
(voir en.wikipedia.org/wiki/Hash_table#Performance_analysis). Lorsqu'un problème est dit "trouver un O(quelque chose) en temps de l'algorithme," c'est toujours pire des cas. Cependant, je ne vais pas donner un -1, puisque, si elle n'est pas la réponse à ce problème particulier, il est la solution que j'utiliserais si j'ai rencontré ce problème dans le monde réel.Arrays.asList(a)
ne fonctionnera pas pour lesint[] a
Une solution simple est, après le tri, déplacer les pointeurs vers le bas à partir de deux extrémités de la pile, de regarder pour les paires que la somme de x. Si la somme est trop élevée, décrémenter le pointeur. Si elle est trop faible, l'accroissement de la gauche. Si les pointeurs de la croix, la réponse est non.
Je pense que j'ai repéré un bug mineur dans votre mise en œuvre, mais les tests doivent découvrir que l'on va très vite.
L'approche est valide, et atteindre la performance souhaitée. Vous pouvez simplifier en remplaçant le itératif de recherche binaire avec un balayage à travers le tableau, en effet remplacer le binaire de recherche par une recherche linéaire qui reprend là où le précédent recherche linéaire à gauche:
Cette étape est O(n). (Montrant que est laissé comme exercice pour vous.) Bien sûr, l'ensemble de l'algorithme prend toujours O(n log n) pour la fusion de tri.
Votre analyse est correcte, et oui, vous devez trier le tableau ou d'autre binaire de recherche ne fonctionne pas.
Ici, c'est une autre solution, en ajoutant quelques conditions dans mergesort.
Mais la complexité de cet algorithme est pas encore égale à THÊTA(nlogn)