Hello,
 
Encore un exo d'algo
 
Etant donné un tabelau de N entiers, entre 1 et N.
Comment determiner si ce tableau possède des duplicats.
 
 
Sylvain

on est pas mardi ?

Ca sent le partiel à plein nez

non non, pas de partiels en vue
 
en fait pu de partiels car j'ai fini mes etudes,  
mais je fais quelques revisions d'algo

 
Fais la somme du tableau et si elle est differente de N*(N+1)/2 y a un duplicat

oui et ?  
 
le tableau 1 5 3 2 4 a pour somme 15
le tableau  1 1 3 4 4 a pour somme 13 != 15 duplicat
etc ... ca me parait trivial.
 
apres pour TROUVER les duplicats ben parcours avec double pointeur du tableau. Tu part de l'indice i que tu compare avec la valeur a l'indice j tant que t[i] != t[j], si tu arrive au bout du tableau, i++ et on repart de i à fin ...
 

bah si tu prend pas un bon exemple ca peut pas marcher
 
1 2 3 4 5 => somme == 15
1 1 4 4 5 => somme == 15

je précise que j'ai trouvé l'exo sous cette forme (avec un S). Ca parait pas simple s'il y a en effet plusieurs duplicats.
 
Peut etre qu'il y aurait en tout 1 duplicat, au quel cas, faire la somme est ok.

Je suppose qu'on a pas droit à une méthode brute force ?

On trie le tableau et on fait un parcours du tableau en verifiant que l'indice est egal à Tab[indice]-1 (en supposant que c'est indicé à partir de 0) et dés que c'est pas le cas on est sur un doublet.
 
Sachant qu'on peut trier un tableau en O(n*log(n)), c'est donc la complexité de cet algo dans le pire des cas.

bah la methode force brute est pas tres tres compliqué
 
un tri par heapsort: O(n*log(n))
puis trouver les duplicats: O(n)
 
Enfin peut etre que y a pas mieux

arf grillé

On peut surement descendre a O(n).

oui,  
Pour O(n), on peut utiliser un tableau a coté pour comptabiliser chaque valeur, et afficher des que l'on repete une de ces valeurs.
 
il y a donc O(n) pour l'algo, et O(n) d'espace

On peut rester constant en espace. On pas vraiement besoin de trier je pense.
En supposant qu'on indice à partir de 0, on boucle en permutant Tab[Tab[i]-1] et Tab[i], ca prend O(n) dans le pire des cas, puis on a plus qu'a faire une recherche de doublons en O(n).
 
Donc le tout est en O(n)  
 
PS: ca marche pas trop mais l'idée est là, j'en suis sur!

si ouais ca marche mais ca utilise o(n) espace
 
Je l'ai pas precisé, mais il y avait trois contraintes dans l'énoncé:
O(n) algo, O(1) espace, ne pas détruire le tableau initial?
(modifier/démodifier le tableau, est-ce le detruire )
 
(remarque, la question était: existe-il un algo O(n), O(1) espace et ne détruisant pas le tableau initial)

ca doit etre faisable, en modifiant le tableau, et puis en le demodifiant je pense
 
->O(n) pour le modifier, trouver les duplicats, O(n) pour le demodifier

Pkoi O(n) en espace, je pige pas ?
 
A mon avis "ne pas detruire le tableau initial" veut dire qu'on doit pouvoir retrouver les memes elements du tableau de depart à chaque instant de l'algo (pas de incr ou de decr).
Si on ne peut pas faire de permutations le O(1) en espace on peut l'oblier.

Ca veut dire quoi "demodifier" ?

C'est pas vraiment O(n) d'espace que tu demandes qu'on t'alloue. Mais quand tu utilises le tableau lui-meme pour reperer tes eventuels doublons, ca veut dire que tu utilise cet espace ...
 
quand tu permutes Tab[Tab[i]-1] et Tab[i] tu modifies le tableau...le dé-modifier ca serait le faire revenir dans son état initial
 
 
En fait, voula une idee que tu viens de me donner en modifiant/demodifiant le tableau:

 
Mais il faut bien un espace non ?    

Et puis pour retrouver le tableau de depart on peut faire une fonction et utiliser l'appel par copie par defaut

Dans l'enonce ils disaient O(n) pour l'algo.
O(1) pour l'espace (ie constant par rapport a n).
et ne pas detruire le tableau.
 
Ambigu -> on peut ne pas detruire le tableau si on le modifie et puis si on le de-modifie.  
 
Je trouve que ca ressemble un peu a O(n) en espace, mais pas tout a fait car on a pas fait de "memory allocation"

arf

Tu fait une incrementation sur un element du tableau, donc tu le detruit ... je sais pas si on peut appeler ca un effet de bord sur le tableau.
 
C'est quoi pour toi O(1) en espace ?

ouais il peut y avoir un effet de bord, s'il y a overflow
remarque qu'on ne detruit pas le tableau si on l'enleve apres..
 
De maniere reccursive il y a surement un moyen simplement de proceder avec des permutations tab[i] / tab[tab[i]] de trouver le premier des duplicats. (mais bon utilisations de la stack a fond ).
 
O(1) en espace, ca veut dire constant par rapport a N.
c'est a dire une allocation constante sur la pile(pas de reccursion), ou bien une allocation constante sur le tas(malloc qui ne depend pas de N).