Trouver des numéros uniques dans la gamme
Eh bien, je dois trouver combien de nombres différents sont dans un tableau.
Par exemple si le tableau est: 1 9 4 5 8 3 1 3 5
La sortie devrait être de 6, car 1,9,4,5,8,3 sont uniques et le 1,3,5 répéter (pas unique).
Donc, voici mon code si loin..... ne fonctionne pas correctement pensé.
#include <iostream>
using namespace std;
int main() {
int r = 0, a[50], n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int j = 0; j < n; j++) {
for (int k = 0; k < j; k++) {
if (a[k] != a[j]) r++;
}
}
cout << r << endl;
return 0;
}
- Trier le tableau, il est alors trivial. Essayez de trouver par vous-même comment la complexité de ce qui se compare à la complexité de votre solution.
- Ce qui semble comme des devoirs à moi... mais oui, vous pouvez trier le tableau, ou vous pouvez utiliser une table de hachage.
- semble ce est un bon endroit pour obtenir les dernières minutes de devoirs à faire. format de question, poster sur de SORTE que, ???, obtenir la réponse!
- Il semble qu'il ne l'est pas - considérant que presque toutes les réponses à ces questions ont soit un mauvais algorithme ou de l'utilisation de la bibliothèque standard pour faire le travail - qui, apparemment, n'est pas ce que les devoirs sont sur ...
- C'est le meilleur de la logique que j'ai jamais trouvé.stackoverflow.com/questions/28320454/...
Vous devez vous connecter pour publier un commentaire.
Permettez-moi de joindre à la fête 😉
Vous pouvez également utiliser une table de hachage:
Pas que cela importe, ici, mais ce sera probablement la meilleure performance pour les grands tableaux.
Si la différence entre le plus petit et le plus grand élément est raisonnablement petit, alors vous pourriez faire quelque chose d'encore plus rapide:
vector<bool>
qui s'étend sur la plage entre min et max de l'élément (si vous saviez les éléments du tableau au moment de la compilation, je vous suggère de lestd::bitset
à la place, mais ensuite, vous pouvez simplement tout calculer au moment de la compilation à l'aide du modèle de méta-programmation de toute façon).vector<bool>
.true
s dans levector<bool>
.Un
std::set
ne contient que des éléments uniques déjà.Comment à ce sujet?
std::set
😛Puisque vous avez déclaré que vous ne pouvez pas utiliser la bibliothèque standard, et doivent utiliser les boucles, nous allons essayer cette solution au lieu de cela.
Je envie vous pas soumettre le présent code comme vos devoirs - du moins pas sans le comprendre. Vous ne faites vous-même un mauvais service, et les chances sont que votre instructeur va savoir que vous n'avez pas à écrire de toute façon: j'ai été un correcteur avant, et il est assez évident lorsque quelqu'un de la qualité du code de magie s'améliore.
n - r
calcule. Il n'est vraiment pas difficile à comprendre; vous pouvez même exécuter le code si vous le devez.3
, pas6
comme pour le problème. Il est comme je l'ai dit: votre code de compte des nombres qui se produisent qu'une seule fois.r
compte tous les cas de numéros qui se produisent à plusieurs reprises - même le premier. L'OP voulait un comte de tous numéros différents. Les solutions en utilisant std::set ou std:: list obtenir ce droit.Je pense que l'emplacement de l'augmentation de la valeur de r est incorrect
Cependant, ma suggestion est en utilisant des algorithmes plus sophistiqués (de cet algorithme est O(N^2)).
if (true == flag)
? Ce dernier est particulièrement effrayant.flag
d'avoir un nom qui raconte ce qu'il veut dire, vous l'apercevez.cela devrait fonctionner, cependant, c'est probablement pas la solution optimale.
Nous pouvons utiliser C++ STL vecteur dans ce programme .
Veuillez sec exécuter votre code
Voir à l'extérieur de la boucle pour chaque élément, il est compté plus d'un à l'intérieur de boucle interne.permettez-nous de dire que la boucle contient 1,2,3,4.1.....les éléments de la marche à vide dans le deuxième itération et la troisième itération 1 est compté comme 1 est 1!=2 ainsi que 1!=3
Maintenant la solution de temps!!