Trouver l'élément répété plus de n/2 fois
Il y a un tableau (de taille N) avec un élément répété plus de N/2 nombre de temps et de la reste de l'élément dans le tableau peut aussi être répété, mais un seul élément est répété plus de N/2 fois. Trouver le nombre.
Je pourrais penser à quelques approches:
- naïf, gardez le compte de chaque nombre dans une carte de hachage.
- le plus simple, trie le tableau et le nombre à n / 2 + 1 ième index est le nombre requis.
- Ne comptez que les valeurs en double consécutives trouver. Vérifier séparément pour le motif où les valeurs sont stockées alternativement.
Impossible de penser à une meilleure solution, il doit y avoir.
7 réponses
Il existe un bel algorithme pour résoudre ce problème qui fonctionne en deux passes (temps total O (n)) en utilisant uniquement un espace externe constant (O (1)). J'ai une implémentation de cet algorithme, avec des commentaires comprenant une preuve d'exactitude, disponible ici
L'intuition derrière l'algorithme est en fait assez beau. Supposons que vous deviez avoir une salle pleine de personnes tenant chacun un élément du tableau. Chaque fois que deux personnes se trouvent là où ni l'un ni l'autre ne tient le même élément de tableau que l'autre, les deux d'entre eux s'assoient. Finalement, à la toute fin, si quelqu'un est laissé debout, il y a une chance qu'ils soient majoritaires, et vous pouvez simplement vérifier cet élément. Tant qu'un élément se produit avec une fréquence d'au moins N / 2, Vous pouvez garantir que cette approche trouvera toujours l'élément majoritaire.
Pour implémenter réellement l'algorithme, vous effectuez un balayage linéaire sur le tableau et gardez une trace de votre supposition actuelle sur l'élément majority est, avec le nombre de fois que vous l'avez vu jusqu'à présent. Initialement, cette supposition est indéfinie et le nombre de répétitions est nul. Lorsque vous traversez le tableau, si l'élément actuel correspond à votre estimation, vous incrémentez le compteur. Si l'élément courant ne correspond pas à votre estimation, vous décrémentez le compteur. Si le compteur atteint zéro, vous le réinitialisez à l'élément suivant que vous rencontrez. Vous pouvez penser à cette mise en œuvre comme une réalisation concrète de ce qui précède " debout dans un chambre " algorithme. Chaque fois que deux personnes se rencontrent avec des éléments différents, ils annulent (laissant tomber le compteur). Chaque fois que deux personnes ont le même élément, elles n'interagissent pas les unes avec les autres.
Pour une preuve d'exactitude complète, une citation à l'article original (par Boyer et Moore du plus célèbre algorithme de correspondance de chaînes Boyer-Moore), et une implémentation en C++, consultez le lien ci-dessus.
C'est le problème de L'élément majoritaire. Il y a un seul passage, algorithme d'espace constant pour ce problème. Voici un bref algorithme codé en python:
import random
items = [1, 2, 3, 4, 5, 5, 5, 5, 5 ]
# shuffle the items
random.shuffle(items)
print("shuffled items: ", items)
majority_elem = items[0]
count = 1
for i in range(1,len(items)):
if items[i] == majority_elem:
count += 1
else:
count -= 1
if count == 0:
majority_elem = items[i]
count = 1
print("majority element : %d" % majority_elem )
Nous utilisons une variable majority_elem pour garder une trace de l'élément majority et un compteur (count)
Initialement, nous définissons le premier élément du tableau comme élément majoritaire.
Nous naviguons à travers la matrice
-
Si l'élément courant = = élément majoritaire: incrément Compter
Else: {nombre de décrémentation. si count devient zéro, définissez count = 1 et définissez majority_element = élément courant. }
Il y a une variation à ce problème, au lieu d'un tableau, il pourrait y avoir une très grande séquence et nous ne connaissons pas la longueur Avant la main. Dans ce cas, le tri ou le partitionnement n'est pas utile.
Références:
- L'Art De La Programmation informatique, fascicule 0: Introduction aux algorithmes combinatoires et aux fonctions booléennes, Volume 0; Volume 4
Si un élément est répété plus de N / 2 fois, alors il doit être la médiane. Il y a de nombreux algorithmes qui vous permettent de trouver efficacement.
Connaissez-vous quicksort? Il a une fonction appelée "partition" qui, pour une valeur donnée, divise le tableau en une section où toutes les valeurs sont supérieures à la valeur (le pivot) sont sur un côté, tandis que toutes les valeurs inférieures à la valeur de l'autre côté. Notez que ce n'est pas une sorte, simplement une séparation. L'élément n / 2 count sera dans la plus grande des deux sections. Vous pouvez appliquer récursivement cette technique pour trouver L'élément dans le temps O(n).
Wikipédia: quicksort, ou Algorithme de sélection générale basé sur une Partition
Dans votre deuxième approche, vous sélectionnez essentiellement l'élément médian. Jetez un oeil à des algorithmes pour trouver la médiane d'une liste de nombres. En particulier, un algorithme de sélection fonctionnerait bien pour cela et le calculerait en O (n).
L'algorithme de sélection de Hoare fonctionne très similaire au tri rapide, sauf qu'au lieu de récurer les deux partitions, il ne récurse qu'une partition (la partition qui contient le kème élément).
En C++, la norme bibliothèque fournit un algorithme de sélection sous la forme de std::nth_element, ce qui garantit O (N) complexité moyenne. Vous pouvez utiliser cette trouver la médiane.
int a[8] = {5, 1, 1, 1, 2, 1, 3, 1};
int median = *std::nth_element(a, a + 4, a + 8);
Notez que std::nth_element va également trier partiellement le tableau en place.
Pas besoin de tri. Vous pouvez simplement utiliser un algorithme de sélection médiane pour déterminer le N / 2-ème élément. QuickSelect s'exécute en O (N) temps prévu. La médiane des médianes s'exécute en O (n).
Trie le tableau en utilisant n'importe quel algorithme de tri. L'élément qui a été répété plus de la moitié du temps sera toujours l'élément moyen.La complexité sera nlog(n).