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,
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
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).