multidisque manipulation des algorithmes

Question

Étant donné un tableau d'entiers, donnent deux entiers à partir du tableau dont l'addition donne un numéro N.

Answer 1

Cela a été récemment couvert sur le blog ihas1337code. Voir la section des commentaires pour les solutions. La manière la plus efficace de résoudre ceci est de placer les nombres dans un hash_map, puis de faire une boucle dans le tableau une deuxième fois en vérifiant chaque élément x si l'élément (N - x) existe dans le hash_map.

Vous pouvez optimiser un peu à partir de là, mais c'est l'idée générale.

Answer 2

Suivez ces étapes:

1.Sort les numéros en utilisant le tri par fusion dans O (n log n) dans l'ordre décroissant (peut être croissant aussi, mais pour ce texte les supposés être classés dans l'ordre desceending).

2.Utilisez deux variables de pointeur l'une pointant vers l'élément de départ (disons p1) et l'autre vers le dernier élément (disons p2).

3.Now ajouter * p1 + * p2 (temp_sum = * p1 + * p2) et le comparer avec la somme nécessaire

Répétez ces étapes jusqu'à ce p1> p2

i.If somme == temp_sum alors notre travail est terminé. Ii) Si somme> temp_sum, alors diminuer p2 pour qu'il pointe vers une valeur plus grande que sa valeur actuelle afin que temp_sum puisse augmenter. Si la somme < temp_sum diminue alors p1 pour faire pointer vers une valeur plus petite que sa valeur actuelle afin que temp_sum puisse diminuer.