arrays - élément - php recherche array




Trouver l'élément major dans le tableau (12)

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 major dans un tableau dans O(n) ?

Exemple d'entrée:

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

Production attendue:

2

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

// Initialise la valeur à chaque indice du tableau avec 0. // Puis itère sur le tableau A, pour chaque valeur de tableau A [i], incrémente 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, retournez 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 est 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));
    }
}

C'est ainsi que je le fais en C ++ en utilisant vector et multimap (JSON avec des clés de répétition).

#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

Il est temps)

Espace: O (n)

Marcher dans l'arbre et compter l'occurrence des éléments dans une table de hachage.

Heure: O (n lg n) ou O (n * m) (dépend du type utilisé)

espace: (1)

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

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

Il est temps)

Espace: O (1)

Parcourez la liste comparez le nombre actuel au nombre actuel le plus probable. Si le nombre est égal au numéro de meilleure estimation actuel incrémenter un compteur, sinon décrémenter le compteur et si le compteur frappe zéro remplacer le numéro de la meilleure estimation actuelle avec le nombre actuel et mettre le compteur à 1. Lorsque vous arrivez à la fin du courant La meilleure estimation est le numéro du candidat, revenez sur la liste juste en comptant les instances du candidat. Si le nombre final est supérieur à n / 2, alors c'est le nombre majoritaire sinon il n'y en a pas.


Il est triste de voir que dans 5 ans, personne n'a écrit une explication appropriée pour ce problème.

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

Clairement, vous pouvez l'approcher avec un hachage ou un tri, mais avec un flux 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 survient plus que tous les autres éléments combinés. C'est-à-dire, si vous comptez le nombre de fois où l'élément majoritaire apparaît, et soustrayez le nombre d'occurrences de tous les autres éléments, vous obtiendrez un nombre positif.

Donc, si vous comptez les occurrences de certains éléments, et soustrayez le nombre d'occurrences de tous les autres éléments et obtenez le nombre 0 - alors 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 flux, si le compteur est 0 - vous remplacez l'élément possible et initialisez le compteur, si le nombre est le même que l'élément possible - augmentez le compteur, sinon diminuez-le. 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 est 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 potentiellement atteindre n (lorsque le tableau est composé des mêmes nombres). Et pour stocker le nombre n vous avez besoin d'un espace O(log (n)) . Donc, du point de vue théorique, c'est l'espace O(n) et l'espace O(log(n)) . De pratique , vous pouvez ajuster 2 ^ 128 nombre dans un longint et ce nombre d'éléments dans le tableau est incroyablement énorme.

Notez également que l'algorithme ne fonctionne que s'il y a un élément majoritaire. Si un tel élément n'existe pas, il renverra encore 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 de Boyer-Moore


Merci pour les réponses précédentes qui m'ont inspiré pour connaître l'algo de Bob Boyer. :)

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

Remarque: un 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();
}

}


Pour trouver la majorité d'un élément dans un tableau, vous pouvez utiliser l'algorithme 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 la suite à l'algorithme de majorité de link Moore et link


Si vous êtes autorisé à créer une table de hachage et que la recherche de hachage est constante, il vous suffit de hash_map chaque entrée par rapport au nombre d'occurrences.

Vous pouvez faire un deuxième passage à travers la table, vous obtenez celui avec le plus grand nombre, mais si vous connaissez à l'avance le nombre d'éléments dans la table, vous saurez immédiatement si nous avons un élément majoritaire sur le premier passage lorsque nous touchons le compte requis sur l'élément.

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

On ne nous dit pas s'il existe une sorte de classement sur le type d'élément, bien que nous devions évidemment pouvoir comparer deux pour l'égalité.


Triez le tableau donné: O (nlogn).

Si la taille du tableau est 7, alors l'élément majoritaire apparaît au moins au plafond (7/2) = 4 fois dans le tableau.

Après que le tableau a été trié, cela signifie que si l'élément majoritaire est d'abord trouvé à la position i, il se trouve également à la position i + floor (7/2) (4 occurences).

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 (indice de tableau à partir de 0.) Si la position 1 + 3 = 4ème élément est également 3, alors cela signifie que 3 est l'élément majoritaire.

si nous faisons une boucle dans 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é totale du temps - O (n).


É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 qui sont différents de e alors e existera jusqu'à la fin si c'est 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 à travers chaque élément et maintient un compte de [maj_index], Si l'élément suivant est identique alors incrémente le compte, si l'élément suivant n'est pas identique alors décrémente le compte, et si le compte atteint 0 alors change maj_index au courant L'élément et les ensembles comptent jusqu'à 1. L'algorithme de la première phase nous donne un élément candidat. Dans la deuxième phase, nous devons vérifier si le candidat est vraiment un élément majoritaire.

La deuxième phase est simple et peut être facilement réalisée en O (n). Nous avons juste besoin de vérifier si le nombre de l'élément candidat est supérieur à n / 2.

Lisez link pour plus de détails


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)
   }

// 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;
}

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;
    }
    }


}

}





time-complexity