[Exigences de question] Vous donnez des nombres et n. Vous devez maintenant trouver le nombre qui se produit plus de 50% des temps dans l'espace O (n) dans O (1).
[Démarrer des conneries] Au début, j'ai vu cette question instantanément aveuglée (tot) / ~~~ (. *). S'il n'y a que le temps nécessaire de O (n), il peut être résolu instantanément avec du hachage (c'est-à-dire avec un espace pour le temps), et il semble difficile de résoudre l'espace d'O (1).
[Pensée 1] Double boucle, c'est la façon la moins efficace de résoudre ce problème, c'est-à-dire de calculer le nombre de fois où il apparaît pour chaque nombre, et la complexité du temps O (n ^ 2) est directement sortie.
[Pensée 2] Premier tri, que les nombres similaires soient disposés ensemble, puis traversent le premier numéro. Donnez maintenant un exemple, tel que: 1000012, maintenant tri: 0000112, commencez à partir de 0, définissez un compteur t = 0, maintenant il y a 4 0s, puis t = 4, constatez que plus de la moitié d'entre eux, sortie 0. Cette méthode est la version optimisée de la méthode précédente.
[Pensée 3] C'est l'idée d'échanger de l'espace contre le temps et le hachage pour faire un tableau unidimensionnel a deux significations. Par exemple, A [x] = y représente que le nombre x apparaît y fois. La complexité du temps de cette méthode est O (n), mais l'espace est vraiment ... Je n'en parlerai pas (* ￣￣)
[Pensée 4] Calculez d'abord la probabilité, sélectionnez le nombre de ces nombres qui sont les plus susceptibles de répondre aux exigences, puis en sélectionnez au hasard quelques-uns. Ce ... oublie ça.
[Pensée 5] Le sujet d'aujourd'hui est le soi-disant algorithme MJRTY, également connu sous le nom d'algorithme de vote majoritaire. Les idées principales sont les suivantes: (Cet algorithme La complexité du temps est O (n)! Il n'y a pas besoin de stockage supplémentaire dans l'espace, donc la complexité de l'espace est O (1) !!!)
Si Count == 0, définissez la valeur du vote sur l'élément actuel du tableau et attribuez le nombre à 1;
Sinon, si les éléments de vote et désormais du tableau ont la même valeur, compter ++, sinon compter;
Répétez les deux étapes ci-dessus jusqu'à ce que le tableau soit scanné.
Le nombre est attribué à 0 et scanne à nouveau le tableau depuis le début. Si la valeur de l'élément de tableau est la même que la valeur du vote, comptez ++ jusqu'à ce que le tableau soit analysé.
Si la valeur du décompte est supérieure ou égale à N / 2 pour le moment, la valeur du vote sera retournée, sinon -1 sera retourné;
Ce qui suit est l'implémentation du code. Étant donné que la question garantit que le résultat doit exister, nous avons omis la dernière étape de la vérification et de la vérification.
Le code clé est le suivant:
#include <ioStream> Utilisation de Namespace Std; int len; void Find (int * a, int n) {char candidat; int ntimes, i; for (i = ntimes = 0; i <n; i ++) {if (ntimes == 0) candidat = a [i], ntimes = 1; else {if (candidat) a [i]) ntimes ++; else ntime -;}} cout << candidate; } int main () {cin >> len; int a [lenCe qui précède est le nombre de plus de la moitié (50%) du nombre d'occurrences qui vous sont présentées par l'éditeur. J'espère que cela vous sera utile. Si vous avez des questions, veuillez me laisser un message et l'éditeur vous répondra à temps. Merci beaucoup pour votre soutien au site Web Wulin.com!