Les tableaux de bits et les tables de hachage ne semblent donc pas permettre une opération de type find-max, mais il existe des moyens de contourner ce problème. Je me demande s'il existe un moyen d'utiliser le tableau de bits seul sans variables supplémentaires, pointeurs, ou en manipulant le début/la fin du tableau, dans certains scénarios. Par exemple ...Tableau de bits avec Find Max
J'ai des entiers {1, ..., n} et un tableau de bits de n bits. Pour conserver un sous-ensemble des entiers, j'utilise l'entier lui-même comme clé dans le tableau de bits et mets le bit à 1 s'il se trouve dans le sous-ensemble, ou 0 s'il ne l'est pas.
Par exemple pour les entiers {1,2,3,4} et le sous-ensemble {1,3), le tableau de bits devrait ressembler à {1,0,1,0}.
Il semble qu'il n'y ait aucun moyen de le faire sans bouger d'une façon ou d'une autre les bits autour de ce qui me porte à croire que le rêve O (1) est mort et peut-être le tableau de bits ne fonctionnera pas. Est-ce que quelque chose comme ceci est possible dans O (log n)?
Merci