On m'a demandé une question d'entrevue pour trouver le nombre de valeurs absolues distinctes entre les éléments du tableau. Je suis venu avec la solution suivante (en C ++) mais l'intervieweur n'était pas content de l'efficacité du temps d'exécution du code.
pour boucle exécute a.size () fois. Cependant, je ne suis pas sûr de l'efficacité de STL std :: Trouver (dans le cas pire, il pourrait être o (n) de sorte que ce code o (n ° C ?
code est: xxx
13 Réponses :
Fondamentalement, remplacez votre std :: Liste avec un STD :: Set. Cela vous donne O (journal (Set.Size ())) recherches + O (1) insertions, si vous faites les choses correctement. De plus, pour l'efficacité, il est logique de mettre en cache le résultat de l'ABS (* IT), bien que cela n'ait qu'un effet minimal (négligeable). L'efficacité de cette méthode est à peu près aussi bonne que possible, sans utiliser de très bon hash (STD :: Set utilise des bin-arbres) ou plus d'informations sur les valeurs du vecteur.
std :: recherche () code> est linéaire (O (n)). J'utiliserais un conteneur associatif trié pour gérer cela, spécifiquement std :: Set . #include <vector>
#include <set>
using namespace std;
int distict_abs(const vector<int>& v)
{
std::set<int> distinct_container;
for(auto curr_int = v.begin(), end = v.end(); // no need to call v.end() multiple times
curr_int != end;
++curr_int)
{
// std::set only allows single entries
// since that is what we want, we don't care that this fails
// if the second (or more) of the same value is attempted to
// be inserted.
distinct_container.insert(abs(*curr_int));
}
return distinct_container.size();
}
Pourquoi ne pas simplement construire distinct_container avec le constructeur de gamme dans ce cas? std :: set
Parce que nous n'étilisons pas directement les valeurs de la source, il y a une transformation ( ABS () dans ce cas) appliquée avant d'insérer. Si ce n'était pas le cas, alors évidemment le constructeur de la plage est le meilleur choix.
Deux points.
std :: La liste est très mauvaise pour la recherche. Chaque recherche est O (n).
utiliser std :: set. L'insertion est logarithmique, il supprime duplicata et est trié. Insérez chaque valeur O (n journal n) puis utilisez le jeu :: Taille pour trouver le nombre de valeurs.
Pour répondre à la partie 2 de votre question, la norme C ++ charge le pire des cas pour les opérations sur les conteneurs et les algorithmes.
trouver : puisque vous utilisez la version de la fonction gratuite de Trouver qui prend des itérateurs , il ne peut rien assumer sur la séquence transmise, il ne peut supposer que la plage est triée, il doit donc traverser chaque article jusqu'à ce qu'il trouve une correspondance, qui est O (N).
Si vous utilisez Set :: Trouvez d'autre part, Ce membre trouve peut utiliser la structure de l'ensemble et ses performances sont nécessaires pour être O (journal n) où n est la taille de l'ensemble.
Oui, ce sera O (n 2 ) - vous finirez par une recherche linéaire pour chaque élément.
Quelques alternatives raisonnablement évidentes seraient d'utiliser un Chaque insertion dans un avec un usered_set, chaque insertion a une complexité constante (attendue), donnant une complexité linéaire dans l'ensemble. std :: Set ou std :: Unorded_sed_set . Si vous n'avez pas de C ++ 0x, vous pouvez remplacer std :: nonOrdered_sed_sed_sed_sed_sed_sed_sed avec TR1 :: Unorded_sed_set_sed_set ou boost :: ONUORDEDED_SET_SED_ / CODE>.
std :: Set est O (log n), de sorte que votre complexité globale est O (n journal n).
Pour répondre à votre deuxième question en premier, oui, le code est Vous avez des options pour l'améliorer. Si la plage de nombres est basse, vous pouvez simplement configurer un réseau suffisamment important et un nombre d'incréments d'incrémentation assez important tout en itérant sur les données source. Si la plage est plus grande mais rare, vous pouvez utiliser une table de hachage d'une sorte pour faire le comptage. Ces deux options sont la complexité linéaire.
Sinon, je ferais une itération pour prendre la valeur ABS de chaque élément, puis les trier, puis vous pouvez faire l'agrégation en une seule passe supplémentaire. La complexité ici est O (n ^ 2) car la complexité de trouve est o (n) .
n journal (n) pour le tri. Les autres passes n'ont pas d'importance pour la complexité.
Je pense qu'un std :: map pourrait également être intéressant:
Pour proposer un code alternatif au code de réglage.
Notez que nous ne voulons pas modifier le vecteur de l'appelant, nous prenons de la valeur. Il vaut mieux laisser copier le compilateur pour nous que de faire la nôtre. S'il est correct de détruire leur valeur, nous pouvons prendre la référence par non-const. L'avantage est que nous ne faisons qu'on allouée / copie une fois si nous décidons de prendre une valeur, Et le reste est terminé sur place tout en vous donnant une complexité moyenne de O (n log n) sur la taille de v .
C'est beaucoup mieux que d'utiliser std :: set
@ John Set est la première chose à venir à l'esprit, mais après une courte promenade, je me suis rendu compte que c'était faisable en place, à la fois coût et très court en utilisant uniquement des algues stl.
Le problème avec les algues STL est parfois que nous avons tendance à les surposer. :) IMHO, le meilleur moyen est de personnaliser l'algorithme QuicksTort telle que lorsque nous partagerons chaque fois que nous obtenons deux éléments égaux, écrasez le deuxième duplicaté avec le dernier élément de la plage, puis réduisez la plage. Cela garantira que vous ne traiterez pas deux fois les éléments en double. Aussi, après une trace rapide, la plage de l'élément est effectuée.
Commenter mon commentaire. Unique sera débarrasser des entrées consécutives. Ainsi, si la plage est triée, tous les doublons sont consécutifs et supprimés.
Distance (unique_end, v.begin ()) n'est pas positif. Vous vouliez probablement dire distance (v.begin (), unique_end) .
Alors que @jerry a dit, d'améliorer un peu sur le thème de la plupart des autres réponses, au lieu d'utiliser une STD :: map ou std :: set que vous pouvez utiliser un STD :: Unordered_map ou STD :: Unommanded_sed (ou l'équivalent de boost).
Cela réduirait les roulements de O (n LG N) ou O (n).
Une autre possibilité, en fonction de la plage des données fournies, vous pourrez peut-être effectuer une variante d'une sorte de radix, bien qu'il n'y ait rien dans la question qui le suggère immédiatement.
Trier la liste avec un type de style Radix pour O (N) Efficacité de l'ISH. Comparer les valeurs adjacentes.
Le meilleur moyen est de personnaliser l'algorithme QuicksTort telle que lorsque nous partagerons chaque fois que nous obtenons deux éléments égaux, écrasez le deuxième duplicaté avec le dernier élément de la plage, puis réduisez la plage. Cela garantira que vous ne traiterez pas deux fois les éléments en double. Aussi, après une trace rapide, la plage de l'élément est la réponse. La complexité est toujours O (N * LG-N), mais cela devrait sauver au moins deux passes sur le tableau.
Les économies sont également proportionnelles à% des doublons. Imaginez s'ils tordent de la question d'origine, «disent que 90% des éléments sont duplicata» ...
Une autre approche:
Efficace spatiale: utilisez la carte de hachage. O (logn) * O (n) pour insertion et gardez simplement le nombre de nombres d'éléments insérés avec succès.
temps efficace: utilisez la table de hachage O (n) pour insertion et maintenez simplement le nombre de nombres insérés avec succès.
Notez que les cartes de hachage ne sont pas aussi efficaces que vous pourriez penser. Surtout comparé à un ensemble simple <>
Par hashmap, je voulais dire un conteneur qui utilise une sorte d'arbre. Ce serait assez d'espace efficace
Vous avez des boucles imbriquées dans votre code. Si vous numérisez chaque élément sur l'ensemble de l'ensemble, il vous donnera une complexité de temps O (N ^ 2) qui n'est pas acceptable dans la plupart des scénarios. C'était la raison pour laquelle le Fusionnez Trier et Quick Trit Algorithmes est venu pour enregistrer les cycles de traitement et les efforts de la machine. Je vous suggérerai de traverser les liens suggérés et de redéfinir votre programme.
Puisque je n'étais pas content de la réponse précédente ici, c'est le mien aujourd'hui. Votre question intiale ne mentionne pas à quel point votre vecteur est grand. Supposons que votre J'aime Je n'ai pu trouver rien vraiment élégant dans la bibliothèque STD, alors voici donc ici Ma proposition (un mélange de std :: vecteur code> est extrêmement grand et avoir très peu de doublons (pourquoi pas?). Cela signifie que l'utilisation d'un autre conteneur (par exemple, std :: Set code>) dupliquera essentiellement votre consommation de mémoire. Pourquoi feriez-vous cela puisque votre objectif est simplement de compter sans dupliquer. @flame code> réponse, mais je n'étais pas vraiment satisfait de l'appel à std :: unique code> . Vous avez passé beaucoup de temps à trier votre vecteur avec soigneusement, puis jetez simplement le tableau de tri pendant que vous pourriez l'utiliser ensuite. P> std :: transformez code> + std :: ABS code> + std :: Trier , mais sans toucher le tableau trié après). p> #include <iostream>
#include <list>
int main()
{
std::list<int> nums {1, 3, 3, 3, 5, 5, 7,8};
std::cout << count_unique( std::begin(nums), std::end(nums) ) << std::endl;
const int array[] = { 0,0,0,1,2,3,3,3,4,4,4,4};
const int n = sizeof array / sizeof * array;
std::cout << count_unique( array, array + n ) << std::endl;
return 0;
}
Le poisson par jour ne vous aidera vraiment pas. Surtout pour l'entretien. Vous devez attraper au moins deux livres sur la structure de données et l'algorithme. My Personnel Beginner Favoris est "Structure de données et algo en C ++" de Sahni, puis continuez à lire "Structure de données utilisant C ++" par Langsam / Tennenbaum. Et en ce qui concerne les questions, vous devez savoir que l'intervieweur vous préoccupe si vous pouvez dériver Bigo. Pas si tu sais. Les PPL sont préoccupés par la mise en oeuvre de bonne réponse. Ils vous donneront ce que vous voulez. Ils ne se soucient pas des choses dont vous avez besoin.
Aussi PAL, s'il vous plaît ne présumez pas que vous devez le coder en C ++, vous devez utiliser des algues STL. Ils sont là pour obtenir de l'aide. Si le besoin est que vous devriez pouvoir les personnaliser. Et cette question est à peu près ce cas exceptionnel lorsque vous devez tordre les algues standard pour l'efficacité.