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 que Math.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 valeur val-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).
InformationsquelleAutor helpermethod | 2010-01-31