Trouver l'élément le plus répété dans un tableau

Question

Étant donné un tableau de N éléments. On sait 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 trouver l'élément qui se répète au moins N/2 fois en un seul passage ou peut-être O(N) ... ? ???

P.S : Aucun espace supplémentaire ne doit être utilisé.

Answer 1

Comme les autres utilisateurs ont déjà affiché l'algorithme, je ne vais pas le répéter. Cependant, je fournis une explication simple de son fonctionnement :

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

Chaque flèche partant du centre représente un candidat différent. Imaginez un point quelque part sur une flèche représentant le compteur et le candidat. Au départ, le compteur est à zéro, il commence donc au centre.
Lorsque le candidat actuel est trouvé, il avance d'un pas dans la direction de cette flèche. Si une valeur différente est trouvée, le compteur se déplace d'un pas vers le centre.
S'il y a une valeur majoritaire, plus de la moitié des déplacements se feront vers cette flèche, et donc l'algorithme se terminera avec le candidat actuel comme valeur majoritaire.

Answer 2

St0le a répondu à la question, mais voici une implémentation en 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 journal, en tout cas) : http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

Answer 3

L'algorithme du vote majoritaire de 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)

Answer 4

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

Une solution consisterait à créer une deuxième liste contenant uniquement les objets uniques de la liste initiale. Ensuite, on crée 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 de la liste.

Une autre façon serait de trier la liste puis de trouver la plus grande section contiguë.

Answer 5

L'algorithme du vote majoritaire de Boyer-Moore ne trouve pas de majorité correcte dans les tableaux d'entrée ci-dessous

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

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