34 votes

Trouver l'élément répété max dans un tableau

Étant donné un tableau avec N éléments. Nous savons que l'un de ces éléments se répète au moins N / 2 fois. Nous ne savons rien des autres éléments. Ils peuvent se répéter ou être uniques.

Existe-t-il un moyen de découvrir l'élément qui se répète au moins N / 2 fois en une seule passe ou peut être O (N) ... ???

PS: aucun espace supplémentaire ne doit être utilisé.

56voto

Nabb Points 2824

Comme les autres utilisateurs ont déjà publié l'algorithme, je ne vais pas le répéter. Cependant, je vais vous donner une explication simple pour expliquer pourquoi cela fonctionne:

Considérons le diagramme suivant, qui est en fait un diagramme d'une lumière non polarisée:

arrows radiating from the centre

Chaque flèche à partir du centre représente un autre candidat. Imaginez un point quelque part sur une flèche représentant le compteur et le candidat. Initialement, le compteur est à zéro, de sorte qu'il commence dans le centre.
Lorsque le candidat est trouvé, il se déplace d'un cran dans le sens de la flèche. Si une valeur différente est trouvé, le compteur se déplace d'un cran vers le centre.
Si il y a une majorité de valeur, plus de la moitié de la passe sera en direction de la flèche, et donc l'algorithme se termine avec l'actuel candidat d'être la majorité de la valeur.

37voto

David Titarenco Points 17148

st0le a répondu à la question, mais voici une implémentation de 5 minutes:

 #include <stdio.h>

#define SIZE 13

int boyerMoore(int arr[]) {
    int current_candidate = arr[0], counter = 0, i;
    for (i = 0; i < SIZE; ++i) {
        if (current_candidate == arr[i]) {
            ++counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        } else if (counter == 0) {
            current_candidate = arr[i];
            ++counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        } else {
            --counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        }
    }
    return current_candidate;
}

int main() {
    int numbers[SIZE] = {5,5,5,3,3,1,1,3,3,3,1,3,3};
    printf("majority: %i\n", boyerMoore(numbers));
    return 0;
}
 

Et voici une explication amusante (plus amusante que la lecture du document, au moins): http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

36voto

st0le Points 15318

L'algorithme de vote majoritaire Boyer-Moore

 //list needs to have an element with a count of more than n/2 throughout itself for
//this algorithm to work properly at all times.

lst = [1,2,1,2,3,1,3,3,1,2,1,1,1]

currentCount = 0
currentValue = lst[0]
for val in lst:
   if val == currentValue:
      currentCount += 1
   else:
      currentCount -= 1

   if currentCount == 0:
      currentValue = val
      currentCount = 1


print(currentValue)
 

0voto

Puddingfox Points 637

Il ne semble pas possible de compter quoi que ce soit sans l'aide de l'espace supplémentaire. Vous avez à stocker au moins un compteur quelque part. Si vous voulez dire que vous ne pouvez pas utiliser plus de O(n) de l'espace, alors il devrait être assez facile.

Un autre moyen serait de créer une seconde liste unique des objets de la liste originale. Ensuite, la création d'une troisième liste de la même longueur que la deuxième avec un compteur pour le nombre d'occurrences de chaque élément dans la liste.

Une autre façon serait de trier la liste puis de trouver le plus grand contigus section.

-2voto

siva Points 338

L'algorithme de vote majoritaire Boyer-Moore ne parvient pas à trouver la majorité correcte dans les tableaux d'entrée ci-dessous

int nombres [SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};

nombres entiers [TAILLE] = {1,2,3,4,1,2,3,4,1,2,3,4,1};

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X