Comment faire pour extraire efficacement les valeurs uniques de la matrice?
J'aimerais extraire les valeurs uniques de mon (allouée dynamiquement) tableau. J'ai quelque chose comme ceci :
[0] 0 int
[1] 1 int
[2] 2 int
[3] 2 int
[4] 2 int
[5] 5 int
[6] 6 int
[7] 6 int
[8] 8 int
[9] 9 int
[10] 10 int
[11] 8 int
[12] 12 int
[13] 10 int
[14] 14 int
[15] 6 int
[16] 2 int
[17] 17 int
[18] 10 int
[19] 5 int
[20] 5 int
Je voudrais avoir une matrice de taille 12 avec chaque enregistrement de la valeur unique de l'autre tableau.
Comment puis-je le faire ?
MODIFIER
J'ai oublié de mentionner que je ne peux pas utiliser des conteneurs STL (comme std::vector
ou std::list
)
Connaissez-vous le maximum et le minimum de vos valeurs dans le tableau alloué dynamiquement?
Je peux obtenir cette valeur oui. Mais dans quel but ?
Pouvez-vous utiliser les algorithmes de la STL?
Non, je ne le peuvent pas.
Je suppose que Jayantha la question est de savoir si les valeurs sont fixes et petits (par une définition de la petite)... probablement l'intention est que vous pouvez créer un tableau de N bool (ou utiliser une image bitmap), de marcher sur le tableau de O(N) marquant les éléments qui sont présents. Puis l'image se contenir l'ensemble des valeurs qui sont présents dans le tableau d'origine.
Je peux obtenir cette valeur oui. Mais dans quel but ?
Pouvez-vous utiliser les algorithmes de la STL?
Non, je ne le peuvent pas.
Je suppose que Jayantha la question est de savoir si les valeurs sont fixes et petits (par une définition de la petite)... probablement l'intention est que vous pouvez créer un tableau de N bool (ou utiliser une image bitmap), de marcher sur le tableau de O(N) marquant les éléments qui sont présents. Puis l'image se contenir l'ensemble des valeurs qui sont présents dans le tableau d'origine.
OriginalL'auteur Patryk | 2012-02-07
Vous devez vous connecter pour publier un commentaire.
D'abord vous avez besoin de trier le tableau, puis itérer sur le tableau trié et vérifiez si l'entrée précédente ou suivante sont les mêmes que l'entrée actuelle. Si non, alors la valeur est unique.
Edit: j'ai peut-être mal compris la question... Une manière d'obtenir ce que vous voulez, c'est de parcourir le tableau. Pour chaque valeur de vérifier la valeur existe déjà dans l'autre tableau, si ce n'est la copie. Cela peut être fait en deux étapes, une fois pour obtenir le nombre des entrées uniques (à l'aide d'un tableau de la même taille que l'existant) et un pour obtenir un tableau de taille correcte.
OriginalL'auteur Some programmer dude
Utilisation std::unique après le tri de votre tableau avec votre favori algorithme de tri (par exemple,std::sort)
Edit:
Sans STL, la solution la plus simple serait de trouver le min & max des valeurs du tableau et de l'allouer dynamiquement un tableau de
bool
. Parcourir le tableau et si vous voyez l'élément, mettre enbool
élément detrue
. Allouer un nouveauint
tableau avec le nombre total d'éléments uniques et de le remplir avec les données de labool
tableau.Recommandé:
Trier le tableau et supprimer des éléments consécutifs. La mise en œuvre de la fonction de tri rapide n'est pas trop dur, et si vous faites affaire avec des entiers, tri radix peut-être mieux.
OriginalL'auteur Jacob
Vous pouvez utiliser un
std::set
. Ajouter tous les éléments, à la fin uniquement les valeurs uniques seront présents.OriginalL'auteur Luchian Grigore
L'objectif principal est de s'assurer que les doublons sont ignorés. Donc, vous devez d'abord trier le tableau, puis en O(n) fois, parcourir le tableau, en ignorant toutes les répétitions. En parcourant le tableau, copie de toutes les valeurs(les valeurs que vous rencontrez pour la première fois) à la nouvelle tableau.
La seule chose que j'ai trouver qui peut vous préoccuper est de l'ordre des éléments dans l'ancien tableau n'est pas conservé dans le nouveau tableau. Mais si vous êtes uniquement intéressé à connaître les valeurs uniques, cette méthode devrait fonctionner correctement.
OriginalL'auteur Archit Kapoor
Vous pouvez utiliser un hash set (unordered_set) pour stocker chaque valeur du tableau source. Le jeu de mise en mémoire automatique des valeurs uniques. Alors, si vous avez vraiment besoin d'un tableau et non pas un jeu, vous pouvez créer un tableau de la bonne taille et le remplir avec les éléments de l'ensemble.
OriginalL'auteur Baptiste Wicht
Si vous connaissez le maximum et le minimum, vous pouvez créer un nouveau tableau avec toutes les valeurs possibles que vous pouvez obtenir et ensuite une boucle sur votre tableau dynamique . Pour chaque valeur de l'ensemble 1 de la nouvelle pile en prenant comme indice de la valeur.
À titre d'exemple:-
disons que vous avez des données de cette
1,2,2,4,6
si la plage est de 1 à 7
le deuxième tableau sera comme ceci
La complexité de l'algo sera 2n
OriginalL'auteur Jayantha Lal Sirisena