A voir également:
- Algorithmique
- Videosurveillance algorithmique - Accueil - Protection
- Exercice en Algorithmique (Boucles) ✓ - Forum Algorithmes / Méthodes
1 réponse
'lut, il ne manque qu'un seul et unique entier dans ce tableau trié? Les entiers, il sont consécutifs de 1?
Si c'est le cas ça peut se faire en O(n); voilà une idée de comment faire:
Si c'est le cas ça peut se faire en O(n); voilà une idée de comment faire:
tableau = [1, 2, 3, ... , n]
Pour i de 0 à longueur (tableau)-1:
Si tableau[i]+1 != tableau[i+1] Alors
// Discontinuité
Afficher "Il manque l'entier" + (tableau[i]+1)
FinSi
FinPour
gravgun : "ça peut se faire en O(n)"
Oups ^^'
Pour faire du O(log n) tu as la recherche par dichotomie.
Cependant la question de gravgun est pertinente, qu'est-ce que tu entends par "ll manque un et un seul entier dans le tableau". Les entiers existent en nombre infinis, alors quel est le sous ensemble que tu manipules ?
M'enfin j'ai dit que c'était une "idée" hein :)
Si tu as par exemple tous les entiers entre 1 et n (sauf celui qui manque) tu sais déjà où chaque entier doit se placer. Par dichotomie tu regardes à partir de quand c'est décalé.
En gros :
l ensemble est de [1..n], par exemple si j ai un tableau qui contient : 0 1 2 3 4 6 7 l'algorithme doit retourner 5.
Avec la dichotomie ça me semble pas mal comme idée mais je trouve pas comment je pourrais faire exactement.....
Par exemple , utilisant la même tableau , si je dévisse le tableau en deux je trouve que m=3 et t[m]=3 si je fais la comparaison
je trouve que t[m-1]+1 = t[m]
t[m+1] -1= t[m]
donc je vais me déplacer ou après ??!!!!