1 réponse
ElementW
Messages postés
4816
Date d'inscription
dimanche 12 juin 2011
Statut
Contributeur
Dernière intervention
5 octobre 2021
1 225
24 mai 2014 à 14:55
24 mai 2014 à 14:55
'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
24 mai 2014 à 15:00
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 ?
24 mai 2014 à 15:02
M'enfin j'ai dit que c'était une "idée" hein :)
24 mai 2014 à 15:03
Modifié par KX le 24/05/2014 à 15:20
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 :
24 mai 2014 à 15:21
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 ??!!!!