Trouvez l’élément majoritaire dans le tableau

L’élément majoritaire est l’élément qui apparaît plus de la moitié de la taille du tableau.

Comment trouver l’élément majoritaire dans un tableau dans O(n) ?

Exemple d’entrée:

 {2,1,2,3,4,2,1,2,2} 

Production attendue:

 2 

L’élément majoritaire (s’il existe) sera également la médiane. Nous pouvons trouver la médiane dans O (n) et vérifier ensuite qu’il s’agit bien d’un élément majoritaire valide dans O (n). Plus de détails pour le lien d’ implémentation

 // returns -1 if there is no element that is the majority element, otherwise that element // funda :: if there is a majority element in an array, say x, then it is okay to discard // a part of that array that has no majority element, the remaining array will still have // x as the majority element // worst case complexity : O(n) int findMajorityElement(int* arr, int size) { int count = 0, i, majorityElement; for (i = 0; i < size; i++) { if (count == 0) majorityElement = arr[i]; if (arr[i] == majorityElement) count++; else count--; } count = 0; for (i = 0; i < size; i++) if (arr[i] == majorityElement) count++; if (count > size/2) return majorityElement; return -1; } 

Il est sortingste de voir que dans 5 ans, personne n’a écrit une explication appropriée à ce problème.

C’est un problème standard dans les algorithmes de streaming (où vous avez un énorme stream de données (potentiellement infini)) et vous devez calculer des statistiques à partir de ce stream, en passant par ce stream une fois.


De toute évidence, vous pouvez aborder le problème avec le hachage ou le sorting, mais avec un stream potentiellement infini, vous pouvez clairement manquer de mémoire. Donc, vous devez faire quelque chose d’intelligent ici.


L’élément majoritaire est l’élément qui apparaît plus de la moitié de la taille du tableau . Cela signifie que l’élément majoritaire apparaît plus que tous les autres éléments combinés. En d’autres termes, si vous comptez le nombre de fois que l’élément majoritaire apparaît et que vous soustrayez le nombre d’occurrences de tous les autres éléments, vous obtenez un nombre positif.

Donc, si vous comptez les occurrences d’un élément et soustrayez le nombre d’occurrences de tous les autres éléments et obtenez le nombre 0, votre élément d’origine ne peut pas être un élément majoritaire. C’est la base d’un algorithme correct:

Déclarez deux variables, counter et possible_element. Itérer le stream, si le compteur est 0 – écraser l’élément possible et initialiser le compteur, si le nombre est le même que possible – augmenter le compteur, sinon le diminuer. Code Python:

 def majority_element(arr): counter, possible_element = 0, None for i in arr: if counter == 0: possible_element, counter = i, 1 elif i == possible_element: counter += 1 else: counter -= 1 return possible_element 

Il est clair que l’algorithme est O(n) avec une très petite constante avant O(n) (comme 3). En outre, il semble que la complexité de l’espace soit O(1) , car nous n’avons que trois variables initialisées. Le problème est que l’une de ces variables est un compteur qui peut éventuellement atteindre n (lorsque le tableau est composé des mêmes numéros). Et pour stocker le nombre n vous avez besoin de l’espace O(log (n)) . Du sharepoint vue théorique, il s’agit donc du temps O(n) et de l’espace O(log(n)) . D’un sharepoint vue pratique , vous pouvez ajuster 2 ^ 128 nombres dans un longint et ce nombre d’éléments dans le tableau est incroyablement grand.

Notez également que l’algorithme ne fonctionne que s’il existe un élément majoritaire. Si un tel élément n’existe pas, il renverra quand même un certain nombre, ce qui sera sûrement faux. (il est facile de modifier l’algorithme pour savoir si l’élément majoritaire existe)

Canal d’histoire: cet algorithme a été inventé quelque part en 1982 par Boyer, Moore et appelé algorithme de vote majoritaire Boyer – Moore

Élément majoritaire:

Un élément majoritaire dans un tableau A [] de taille n est un élément qui apparaît plus de n / 2 fois (et donc il y a au plus un tel élément).

Trouver un candidat:

L’algorithme de la première phase qui fonctionne dans O (n) est connu sous le nom d’algorithme de vote de Moore. L’idée de base de l’algorithme est que si nous annulons chaque occurrence d’un élément e avec tous les autres éléments différents de e, e existera jusqu’à la fin s’il s’agit d’un élément majoritaire.

 findCandidate(a[], size) 1. Initialize index and count of majority element maj_index = 0, count = 1 2. Loop for i = 1 to size – 1 (a)If a[maj_index] == a[i] count++ (b)Else count--; (c)If count == 0 maj_index = i; count = 1 3. Return a[maj_index] 

L’algorithme ci-dessus boucle chaque élément et maintient un décompte de [maj_index]. Si l’élément suivant est identique, incrémente le compte, si l’élément suivant n’est pas le même, puis décrémente le compte et si le compte atteint 0, change le maj_index élément et ensembles compte à 1. L’algorithme de première phase nous donne un élément candidat. Dans un deuxième temps, nous devons vérifier si le candidat est vraiment un élément majoritaire.

La deuxième phase est simple et peut être facilement effectuée dans O (n). Il suffit de vérifier si le nombre d’éléments candidats est supérieur à n / 2.

Lire geeksforgeeks pour plus de détails

Il est temps)

Espace: O (n)

Parcourez l’arborescence et comptez l’occurrence des éléments dans une table de hachage.

Time: O (ng n) ou O (n * m) (dépend du type utilisé)

espace: (1)

sortinger le tableau puis compter les occurrences des éléments.

L’interview réponse correcte: l’algorithme de vote de Moore

Il est temps)

Espace: O (1)

Parcourez la liste, comparez le nombre actuel au meilleur nombre actuel estimé. Si le nombre est égal au meilleur nombre de devinettes actuel, incrémentez un compteur, sinon décrémentez le compteur et si le compteur atteint zéro, remplacez le meilleur chiffre actuel par le nombre actuel et mettez le compteur à 1. Lorsque vous atteignez la fin il vaut mieux deviner le numéro du candidat, parcourez à nouveau la liste en comptant les instances du candidat. Si le décompte final est supérieur à n / 2, alors c’est le nombre majoritaire, sinon il n’y en a pas.

Que diriez-vous d’une approche d’échantillonnage aléatoire? Vous pouvez échantillonner, disons des éléments sqrt (n) et pour chaque élément plus de sqrt (n) / 4 fois (peut être accompli naïvement dans O (n) time et O (sqrt (n)) space), vous pouvez vérifier si c’était un élément majoritaire en O (n) temps.

Cette méthode trouve la majorité avec une probabilité élevée car l’élément majoritaire serait échantillonné au moins sqrt (n) / 2 fois dans l’espérance, avec un écart type d’au plus n ^ {1/4} / 2.

Une autre approche d’échantillonnage similaire à une approche que j’ai vue dans l’un des liens en double consiste à dessiner deux échantillons, et s’ils sont égaux, vérifiez que vous avez trouvé l’élément majoritaire dans le temps O (n). L’étape supplémentaire de vérification est nécessaire car les autres éléments, outre la majorité, peuvent ne pas être distincts.

En algorithme de Monte-Carlo,

 Majority (a,n) //a[]-array of 'n' natural numbers { j=random(0,1,....,n-1) /*Selecting the integers at random ranging from 0 to n-1*/ b=a[j];c=0; for k from 0 to n-1 do { if a[k]=b then, c=c+1; } return (c>n/2) } 

Pour trouver la majorité d’un élément dans un tableau, vous pouvez utiliser l’algorithme de vote majoritaire de Moore, qui est l’un des meilleurs algorithmes.

Complexité temporelle: O(n) or linear time

Complexité de l’espace: O(1) or constant space

Lire plus à l’algorithme de vote majoritaire de Moore et GeeksforGeeks

Si vous êtes autorisé à créer une table de hachage et à supposer que la recherche par entrée de hachage est constante, vous devez simplement hash_map pour chaque entrée par rapport au nombre d’occurrences.

Vous pouvez faire un deuxième passage à travers la table dont vous avez le nombre le plus élevé, mais si vous connaissez à l’avance le nombre d’éléments dans le tableau, vous saurez immédiatement si nous avons un élément majoritaire au premier passage. compte nécessaire sur l’élément.

Vous ne pouvez pas garantir bien sûr qu’il y a même une séquence de 2 occurrences consécutives de l’élément, par exemple 101010101010101010101 n’a pas de 1 consécutif mais c’est un élément majoritaire.

On ne nous dit pas s’il y a un ordre quelconque sur le type d’élément, bien que nous devions évidemment être en mesure de comparer deux types d’égalité.

  int majorityElement(int[] num) { int major=num[0], count = 1; for(int i=1; i 

Complexité temporelle O (n)

 public class MajorityElement { public static void main(Ssortingng[] args) { int arr[]={3,4,3,5,3,90,3,3}; for(int i=0;i=arr.length/2) { System.out.println("majority element"+arr[i]); break; } } } 

}

Une version modifiée de l’algorithme de Boyer,

  • 3 passes où,
    • Au premier passage, nous effectuons une itération avant du tableau
    • Dans la seconde passe, nous effectuons une itération inverse du tableau.
    • Au troisième passage, obtenez des comptes pour les deux éléments majoritaires obtenus lors des première et deuxième passes.

Techniquement, un algorithme de complexité linéaire (O (3n)). Je crois que cela devrait fonctionner pour un tableau avec un élément majoritaire qui se produit au moins n / 2 fois.

 #include  #include  template  DataType FindMajorityElement(std::vector arr) { // Modified BOYERS ALGORITHM with forward and reverse passes // Count will stay positive if there is a majority element auto GetMajority = [](auto seq_begin, auto seq_end) -> DataType{ int count = 1; DataType majority = *(seq_begin); for (auto itr = seq_begin+1; itr != seq_end; ++itr) { count += (*itr == majority) ? 1 : -1; if (count <= 0) { // Flip the majority and set the count to zero whenever it falls below zero majority = *(itr); count = 0; } } return majority; }; DataType majority1 = GetMajority(arr.begin(), arr.end()); DataType majority2 = GetMajority(arr.rbegin(), arr.rend()); int maj1_count = 0, maj2_count = 0; // Check if any of the the majority elements is really the majority for (const auto& itr: arr) { maj1_count += majority1 == itr ? 1 : 0; maj2_count += majority2 == itr ? 1 : 0; } if (maj1_count >= arr.size()/2) return majority1; if (maj2_count >= arr.size()/2) return majority2; // else return -1 return -1; } 

Code testé ici

Merci pour les réponses précédentes qui m’ont inspiré à connaître l’algo de Bob Boyer. 🙂

Version générique Java: une version modifiée de l’algorithme de Boyer

Note: le tableau de type primitif peut utiliser le wrapper.

 import com.sun.deploy.util.ArrayUtil; import com.sun.tools.javac.util.ArrayUtils; /** * Created by yesimroy on 11/6/16. */ public class FindTheMajority { /** * * @param array * @return the value of the majority elements */ public static  E findTheMajority(E[] array){ E majority =null; int count =0; for(int i=0; i (array.length /2)){ return majority; }else{ return null; } } public static void main(Ssortingng[] args){ Ssortingng[] test_case1 = {"Roy","Roy","Roy","Ane","Dan","Dan","Ane","Ane","Ane","Ane","Ane"}; Integer[] test_case2 = {1,3,2,3,3,3,3,4,5}; System.out.println("test_case1_result:" + findTheMajority(test_case1)); System.out.println("test case1 the number of majority element should greater than" + test_case1.length/2); System.out.println(); System.out.println("test_case2_result:" + findTheMajority(test_case2)); System.out.println("test case2 the number of majority element should greater than" + test_case2.length/2); System.out.println(); } 

}

// Supposons qu’on nous donne un tableau A. // Si nous avons tous les éléments du tableau donné, chaque élément est inférieur à K, alors nous pouvons créer un tableau supplémentaire B de longueur K + 1.

// Initialise la valeur à chaque index du tableau avec 0. // Ensuite, parcourez le tableau donné A, pour chaque valeur de tableau A [i], incrémentez la valeur avec 1 à l’index correspondant A [i] dans le tableau créé B.

// Après avoir parcouru le tableau A, parcourez maintenant le tableau B et trouvez la valeur maximale. Si vous trouvez la valeur supérieure à la valeur n / 2, renvoyez cet index particulier.

// La complexité temporelle sera O (n + K) si K <= n alors équivalent à O (n).

// Nous avons une contrainte ici que tous les éléments du tableau sont O (K). // En supposant que chaque élément est inférieur ou égal à 100, dans ce cas, K vaut 100.

 import javax.print.atsortingbute.standard.Finishings; public class MajorityElement { private static int maxElement=100; //Will have all zero values initially private static int arrB[]=new int[maxElement+1]; static int findMajorityElement(int[] arrA) { int count = 0, i, majorityElement; int n=arrA.length; for (i = 0; i < n; i++) { arrB[arrA[i]]+=1; } int maxElementIndex=1; for (i = 2; i < arrB.length; i++){ if (arrB[i]>n/2) { maxElementIndex=i; break; } } return maxElementIndex; }` public static void main(Ssortingng[] args) { int arr[]={2,6,3,2,2,3,2,2}; System.out.println(findMajorityElement(arr)); } } 

Cela vous aidera et si deux éléments répètent le même nombre de fois si ne montreront aucun.

 int findCandidate(int a[], int size) { int count,temp=0,i,j, maj; for (i = 0; i < size; i++) { count=0; for(j=i;jtemp) { temp=count; maj=i; } else if(count==temp) { maj=-1; } } return maj; } 

Voici comment je le fais en C ++ en utilisant vector et multimap (JSON avec des clés de répétition).

 #include  #include  #include  #include  #include  using namespace std; vector  majorityTwoElement(vector  nums) { // declare variables multimap  nums_map; vector  ret_vec, nums_unique (nums); int count = 0; bool debug = false; try { // get vector of unique numbers and sort them sort(nums_unique.begin(), nums_unique.end()); nums_unique.erase(unique(nums_unique.begin(), nums_unique.end()), nums_unique.end()); // create map of numbers and their count for(size_t i = 0; i < nums_unique.size(); i++){ // get number int num = nums_unique.at(i); if (debug) { cout << "num = " << num << endl; } // get count of number count = 0; // reset count for(size_t j = 0; j < nums.size(); j++) { if (num == nums.at(j)) { count++; } } // insert number and their count into map (sorted in ascending order by default) if (debug) { cout << "num = " << num << "; count = " << count << endl; } nums_map.insert(pair (count, num)); } // print map if (debug) { for (const auto &p : nums_map) { cout << "nums_map[" << p.first << "] = " << p.second << endl; } } // create return vector if (!nums_map.empty()) { // get data auto it = prev(nums_map.end(), 1); auto it1 = prev(nums_map.end(), 2); int last_key = it->first; int second_last_key = it1->first; // handle data if (last_key == second_last_key) { // tie for repeat count ret_vec.push_back(it->second); ret_vec.push_back(it1->second); } else { // no tie ret_vec.push_back(it->second); } } } catch(const std::exception& e) { cerr << "e.what() = " << e.what() << endl; throw -1; } return ret_vec; } int main() { vector  nums = {2, 1, 2, 3, 4, 2, 1, 2, 2}; try { // get vector vector  result = majorityTwoElement(nums); // print vector for(size_t i = 0; i < result.size(); i++) { cout << "result.at(" << i << ") = " << result.at(i) << endl; } } catch(int error) { cerr << "error = " << error << endl; return -1; } return 0; } // g++ test.cpp // ./a.out 

Triez le tableau donné: O (nlogn).

Si la taille du tableau est 7, alors l’élément majoritaire se produit au moins au plafond (7/2) = 4 fois dans le tableau.

Une fois le tableau sortingé, cela signifie que si l’élément majoritaire est d’abord trouvé à la position i, il se trouve également à la position i + étage (7/2) (4 occurrences).

Exemple – Tableau donné A – {7,3,2,3,3,6,3}

Trier le tableau – {2,3,3,3,3,6,7}

L’élément 3 se trouve à la position 1 (index de tableau à partir de 0). Si la position 1 + 3 = 4ème élément est également 3, cela signifie que 3 est l’élément majoritaire.

si nous parcourons le tableau depuis le début ..

comparer la position 0 avec la position 3, les différents éléments 2 et 3. comparer la position 1 avec la position 4, même élément. Nous avons trouvé notre match majoritaire!

Complexité – O (n)

Complexité temporelle totale – O (n).