Bonjour,
J'ai un petit souci par rapport aux algorithmes de tri.
En effet, il faudrait trouver un algorithme qui tri un tableau T de taille n et qui contient des 0 et des 1 dans un ordre quelconque et retourner le nombre des 0 et 1 sans les compter explicitement.
Sauf que cet algo doit être linéaire et de complexité spatiale O(1).
J'ai regardé les algo linéaires counting sort, radix sort, bucket sort mais tous ces tris utlisent un 2e tableau et donc de complexité spatiale sup a O(1).
Avez vous une idée de comment je pourrais procéder?
Merci,
