Trouver l'élément majoritaire dans array

// 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 triste de voir que dans 5 ans, personne n'a écrit une bonne explication pour ce problème.

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

il est clair que vous pouvez l'aborder avec le hachage ou le tri, mais avec un flux potentiellement infini, vous pouvez clairement manquer de mémoire. Donc tu dois faire quelque chose d'intelligent ici.

l'élément majoritaire est l'élément qui se produit plus de la moitié de la taille du tableau . Cela signifie que l'élément majoritaire se produit plus que tous les autres éléments combinés. C'est, si vous comptez le nombre de fois que la majorité de l'élément s'affiche, et soustraire le nombre d'occurrences de tous les autres éléments, vous obtiendrez 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 - alors votre élément original ne peut pas être un élément majoritaire. C'est la base d'un algorithme correct:

déclarer deux variables, counter et possible_element. Itérer le flux, si le compteur est 0 - votre remplacer l'élément possible et initialiser le compteur, si le nombre est le même que possible élément - augmenter le compteur, au contraire 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 de voir que l'algorithme est O(n) avec une très petite constante avant O(n) (3). Il semble aussi que la complexité de l'espace est O(1) , parce que nous avons seulement trois variables initialisées. Le problème est que l'une de ces variables est un compteur qui peut potentiellement atteindre n (lorsque le tableau se compose des mêmes nombres). Et pour stocker le numéro n vous avez besoin de O(log (n)) espace. Donc du point de vue théorique c'est O(n) temps et O(log(n)) espace. de pratique , vous pouvez ajuster 2^128 nombre dans un longint et ce nombre d'éléments dans le tableau est incroyablement énorme.

noter également que l'algorithme ne fonctionne que s'il y a un élément majoritaire. Si un tel élément n'existe pas, il reviendra encore un certain nombre, qui sera sûrement tort. (il est facile de modifier l'algorithme pour dire si l'élément majoritaire existe)

History channel: cet algorithme a été inventé quelque part en 1982 par Boyer, Moore et appelé Boyer–Moore majority vote algorithm

É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 pour la première phase qui fonctionne dans O(n) est connu comme L'algorithme de vote de Moore. L'idée de base de l'algorithme est que si on annule chaque occurrence d'un élément e avec tous les autres éléments qui sont différents de e, alors e existera jusqu'à la fin si c'est une majorité de l'élément.

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]

boucle l'algorithme ci-dessus à travers chaque élément et maintient un compte d'un[maj_index], si l'élément suivant est le même augmente alors le compte, si l'élément suivant n'est pas le même alors décrète le compte, et si le compte atteint 0 change alors le maj_index à l'élément courant et fixe le compte à 1. L'algorithme de la première Phase nous donne un élément candidat. En deuxième phase nous devons vérifier si le candidat est vraiment un élément majoritaire.

Deuxième phase est simple et peut être facilement fait en O(n). Nous devons juste vérifier si le nombre de l'élément candidat est supérieur à n/2.

Lire geeksforgeeks pour plus de détails

de Temps:O(n)

de l'Espace:O(n)

promenez-vous dans l'arbre et comptez la présence d'éléments dans une table de hachage.

de Temps:O(n lg n) ou O(n*m)(dépend de la sorte utilisée)

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

L'interview réponse correcte: Moore Algorithme de Vote

de Temps: O(n)

De L'Espace:O(1)

parcourez la liste comparez le nombre courant vs le nombre actuel de la meilleure estimation. Si le nombre est égal au nombre de la meilleure estimation courante incrémenter un compteur, sinon décrémenter le compteur et si le compteur frappe zéro remplacer le nombre de la meilleure estimation courante avec le nombre courant et régler le compteur à 1. Lorsque vous arrivez à la fin de la meilleure estimation actuelle est le nombre de candidat, parcourez la liste à nouveau en comptant les instances du candidat. Si la finale le nombre est supérieur à n / 2 alors c'est le nombre de la majorité sinon il n'y en a pas.

Comment une approche d'échantillonnage aléatoire? Vous pouvez échantillonner, par exemple les éléments sqrt(n) et pour chaque élément qui s'est produit plus que sqrt(n) / 4 fois (peut être accompli naïvement dans O(n) temps et O(sqrt(n)) espace), vous pouvez vérifier si c'était un élément majoritaire dans O(N) temps.

cette méthode trouve la majorité avec une forte probabilité parce que l'élément de Majorité serait échantillonné au moins deux fois sqrt( n) / 2 en attente, avec un écart-type d'au plus n^1/4} / 2.

une autre méthode d'échantillonnage qui est semblable à une méthode que j'ai vue dans l'un des liens dupliqués est de tirer deux échantillons, et s'ils sont égaux vérifier que vous avez trouvé l'élément majoritaire dans O(n) temps. L'étape de vérification supplémentaire est nécessaire parce que les autres éléments en plus de la majorité peuvent ne pas être distincts.

dans l'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 alors vous pouvez utiliser L'algorithme de vote majoritaire de Moore qui est l'un des meilleurs algorithmes pour elle.

Complexité Temporelle: O(n) or linear time

Complexité De L'Espace: O(1) or constant space

Lire la suite de Moore Vote à la Majorité de l'Algorithme de et GeeksforGeeks

si vous êtes autorisé à créer une table de hachage et de supposer la recherche de hachage-entrée est constante, vous hash_map juste chaque entrée par rapport au nombre d'occurrences.

vous pouvez faire un second passage à travers la table vous obtenez celui avec le nombre le plus élevé, mais si vous connaissez à l'avance le nombre d'éléments dans la table, vous saurez immédiatement si nous avons un élément de Majorité sur le premier passage lorsque nous frappons le nombre requis sur l'élément.

vous ne pouvez pas garantie bien sûr qu'il y a même une séquence de 2 occurrences consécutives de l'élément eg 1010101010101010101010101 n'a pas de 1s consécutif mais c'est un élément majoritaire.

on ne nous dit pas s'il y a une sorte d'ordre sur le type d'élément bien qu'évidemment nous devons être en mesure de comparer deux pour l'égalité.

    int majorityElement(int[] num) {
       int major=num[0], count = 1;
       for(int i=1; i<num.length;i++){
           if(count==0){
               count++;
               major=num[i];
           }
           else if(major==num[i]){
                    count++;
           }
           else 
               count--;
   }            
    return major;
}

Complexité temporelle O(n)

public class MajorityElement
    {
       public static void main(String[] args) 
          {
             int arr[]={3,4,3,5,3,90,3,3};

              for(int i=0;i<arr.length;i++)
                {
                  int count=0;
                   int j=0;

                    while(j<arr.length-1)
                     { 
                        if(i==j)
                        j=j+1;
                          if(arr[i]==arr[j])
                            count++;
                          j++;
                                  }

                             if(count>=arr.length/2)
                               {
                              System.out.println("majority element"+arr[i]);
                                   break;
    }
    }


}

}

une version modifiée de L'algorithme de Boyer,

• 3 passes where,
  • dans le premier passage, nous faisons une itération avant du tableau
  • dans le second passage, nous faisons une itération inverse du tableau.
  • dans le troisième passage, obtenir des comptes pour les deux éléments majoritaires obtenus dans les première et deuxième passes.

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

#include <iostream>
#include <vector>

template <typename DataType>
DataType FindMajorityElement(std::vector<DataType> 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é de connaître Argo de Bob Boyer. :)

version Java generic: une version modifiée de L'algorithme de Boyer

Note: le tableau de type primitif peut utiliser 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> E findTheMajority(E[] array){
    E majority =null;
    int count =0;

    for(int i=0; i<array.length; i++){
        if(count==0){
            majority = array[i];
        }
        if(array[i].equals(majority)){
            count++;
        }else{
            count--;
        }

    }

    count = 0;
    for(int i=0; i<array.length ; i++){
        if(array[i].equals(majority)){
            count++;
        }
    }

    if(count > (array.length /2)){
        return majority;
    }else{
        return null;
    }
}

public static void main(String[] args){
    String[] 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 dans le tableau donné tels que chaque élément est inférieur à K, alors nous pouvons créer un tableau supplémentaire B avec la longueur K+1.

//initialise la valeur à chaque indice du tableau avec 0. // Puis, itérer à travers le tableau donné A, pour chaque valeur de tableau A[i], incrémenter la valeur avec 1 à l'index correspondant A[i] dans le tableau créé B.

/ / après itération à travers le tableau a, maintenant parcourir le tableau B et de trouver la valeur maximale. Si vous trouvez que la valeur est supérieure à n/2, Retournez l'indice en question.

//Temps de Complexité 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 est de 100.

import javax.print.attribute.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(String[] 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 montrent 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;j<size;j++)
{
    if(a[j]==a[i])
    count++;
}
if(count>temp)
{   
    temp=count;
    maj=i;
}
else if(count==temp)
{   
    maj=-1; 
}
}


return maj;
}

C'est comme ça que je le fais en C++ en utilisant vector et multimap (JSON avec les touches repeat).

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <iterator>

using namespace std;

vector <int> majorityTwoElement(vector <int> nums) {
  // declare variables
  multimap <int, int> nums_map;
  vector <int> 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<int, int> (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 <int> nums = {2, 1, 2, 3, 4, 2, 1, 2, 2};

  try {
    // get vector
    vector <int> 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

trier le tableau donné: O (nlogn).

si la taille du tableau est 7, alors l'élément majoritaire se produit plafond le plus bas(7/2) = 4 fois dans le tableau.

après le tri du tableau, cela signifie que si l'élément majoritaire se trouve d'abord en position i, il se trouve aussi en position I + plancher(7/2) (4 occurences).

exemple de tableau a - {7,3,2,3,3,6,3,3}

trier le tableau - {2,3,3,3,3,6,7,7}

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

si on boucle à travers le tableau depuis le début..

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

Complexité O(n)

Temps Total de complexité O(n).