Discussion :

[tnarol]

Salut,

Je cherche la réponse à un test de recrutement sur lequel j'ai coincé :
J'ai un tableau de taille N qui contient tous les nombres entre 1 et N dans un ordre aléatoire. A ce tableau je retire un nombre et je le remplace par un autre. Comment trouver le nombre qui a disparu et le nombre qui est présent en double en ne parcourant qu'une fois le tableau (algo en O(N)) ?

[CedricMocquillon]

Tu crées un tableau T de taille N initialisé à 0, tu boucles sur les éléments de ton tableau Src et tu fais T[Src[i]] += 1
A la fin tu boule sur T et tu mémorises les positions pour lesquelles tu as soit 0 soit 2.
L'algo est en O(2*N) ~ O(N)

[10_GOTO_10]

Tu calcules en un seul passage la somme des termes du tableau et la somme des carrés des termes. Connaissant la somme théorique des nombres (des carrés des nombres) de 1 à N, tu peux en déduire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
x - y = a
x² - y² = b

(où x est le nombre qui a été remplacé par y)

Tu remplaces y par (x - a) dans la seconde équation, tu résoud, et tu as x, puis y facilement.

[CedricMocquillon]

Joli! Juste une remarque pour le PO: la complexité des deux algos proposés est identique; le fait que je propose de boucler 2 fois sur le tableau est équivalent à la proposition de 10_GOTO_10 de calculer la somme cumulée + la somme cumulée des carrés. Cependant, la méthode de 10_GOTO_10 est bien plus avantageuse au niveau occupation mémoire (deux entiers à mémoriser au lieu d'un tableau à allouer). En tout cas, je suis fan de l'approche mathématique proposé par 10_GOTO_10