Encontre o elemento majoritário na matriz

O elemento majoritário é o elemento que ocorre mais da metade do tamanho do array.

Como encontrar o elemento majoritário em uma matriz em O(n) ?

Exemplo de input:

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

Produção esperada:

 2 

O elemento majoritário (se existir) também será a mediana. Podemos encontrar a mediana em O (n) e então verificar que é de fato um elemento majoritário válido em O (n). Mais detalhes para o link de implementação

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

É triste ver que em 5 anos ninguém escreveu uma explicação adequada para este problema.

Este é um problema padrão nos algoritmos de streaming (onde você tem um stream enorme (potencialmente infinito) de dados) e você precisa calcular algumas statistics desse stream, passando por esse stream uma vez.


É claro que você pode abordá-lo com hashing ou sorting, mas com um stream potencialmente infinito você pode ficar sem memory. Então você tem que fazer algo inteligente aqui.


O elemento majoritário é o elemento que ocorre mais da metade do tamanho do array . Isso significa que o elemento majoritário ocorre mais que todos os outros elementos combinados. Ou seja, se você contar o número de vezes que o elemento majoritário aparece e subtrair o número de ocorrências de todos os outros elementos, você receberá um número positivo.

Portanto, se você contar as ocorrências de algum elemento e subtrair o número de ocorrências de todos os outros elementos e obter o número 0, seu elemento original não poderá ser um elemento majoritário. Esta é a base para um algoritmo correto:

Declare duas variables, counter e possible_element. Iterar o stream, se o contador for 0 – você sobrescreve o possível elemento e inicializa o contador, se o número for o mesmo que o elemento possível – aumente o contador, caso contrário, diminua-o. Código 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 

É claro que o algoritmo é O(n) com uma constante muito pequena antes de O(n) (como 3). Também parece que a complexidade do espaço é O(1) , porque temos apenas três variables ​​inicializadas. O problema é que uma dessas variables ​​é um contador que potencialmente pode crescer até n (quando a matriz consiste nos mesmos números). E para armazenar o número n você precisa de O(log (n)) espaço. Então, do ponto de vista teórico , é O(n) tempo e O(log(n)) espaço. Da prática , você pode ajustar o número 2 ^ 128 em um longint e esse número de elementos no array é inimaginavelmente grande.

Observe também que o algoritmo funciona somente se houver um elemento majoritário. Se tal elemento não existir, ainda retornará algum número, o que certamente será errado. (é fácil modificar o algoritmo para dizer se o elemento majoritário existe)

Canal de história: este algoritmo foi inventado em algum lugar em 1982 por Boyer, Moore e chamado algoritmo de voto majoritário de Boyer-Moore

Elemento Majoritário:

Um elemento majoritário em uma matriz A [] de tamanho n é um elemento que aparece mais de n / 2 vezes (e, portanto, há no máximo um desses elementos).

Encontrando um Candidato:

O algoritmo para a primeira fase que funciona em O (n) é conhecido como Algoritmo de Votação de Moore. A ideia básica do algoritmo é se nós cancelarmos cada ocorrência de um elemento e com todos os outros elementos que são diferentes de e então existiremos até o final se for um elemento majoritário.

 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] 

O algoritmo acima percorre cada elemento e mantém uma contagem de um [maj_index], se next element for mesmo, incrementa a contagem, se next element não for o mesmo, decrementa a contagem e, se a contagem atingir 0, altera o maj_index para o atual element e sets count para 1. O algoritmo First Phase nos dá um elemento candidato. Na segunda fase, precisamos verificar se o candidato é realmente um elemento majoritário.

A segunda fase é simples e pode ser feita facilmente em O (n). Nós só precisamos verificar se a contagem do elemento candidato é maior que n / 2.

Leia geeksforgeeks para mais detalhes

Tempo: O (n)

Espaço: O (n)

Ande na tree e conte a ocorrência de elementos em uma tabela de hash.

Tempo: O (n lg n) ou O (n * m) (depende do tipo usado)

espaço: (1)

classifique a matriz e conte as ocorrências dos elementos.

A resposta correta da entrevista: Algoritmo de votação de Moore

Tempo: O (n)

Espaço: O (1)

Percorra a lista e compare o número atual com o número atual de melhor palpite. Se o número for igual ao número de melhor palpite atual, incremente um contador, caso contrário, diminua o contador e, se o contador atingir zero, substitua o número atual de melhor palpite pelo número atual e configure o contador para 1. Quando chegar ao fim, o número atual O melhor palpite é o número do candidato, percorrer a lista novamente contando apenas as instâncias do candidato. Se a contagem final for maior que n / 2, então é o número majoritário, caso contrário não há um.

Como sobre uma abordagem de amostragem aleatória? Você poderia provar, digamos, elementos sqrt (n) e para cada elemento que ocorreu mais que sqrt (n) / 4 vezes (pode ser realizado ingenuamente em tempo O (n) e espaço O (sqrt (n))), você pode verificar se foi um elemento majoritário no tempo O (n).

Este método encontra a maioria com alta probabilidade porque o elemento majoritário seria amostrado pelo menos sqrt (n) / 2 vezes na expectativa, com um desvio padrão de no máximo n ^ {1/4} / 2.

Outra abordagem de amostragem semelhante a uma abordagem que vi em um dos links duplicados é desenhar duas amostras e, se forem iguais, verifique se você encontrou o elemento majoritário no tempo O (n). A etapa de verificação adicional é necessária porque os outros elementos, além da maioria, podem não ser distintos.

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

Para encontrar a maioria de um elemento em uma matriz, você pode usar o Algoritmo de Votação da Maioria de Moore, que é um dos melhores algoritmos para ele.

Complexidade do Tempo: O(n) or linear time

Complexidade do espaço: O(1) or constant space

Leia mais no algoritmo de voto de maioria de Moore e GeeksforGeeks

Se você tem permissão para criar uma tabela de hash e assumir que a consulta de input de hash é constante, você apenas hash_map cada input contra o número de ocorrências.

Você pode fazer uma segunda passagem pela mesa e obter a que tem a maior contagem, mas se souber antecipadamente o número de elementos na tabela, você saberá imediatamente se tivermos um elemento majoritário na primeira passagem quando atingirmos a contagem necessária no elemento.

Você não pode garantir, é claro, que haja mesmo uma sequência de 2 ocorrências consecutivas do elemento, por exemplo, 1010101010101010101 não possui 1s consecutivos, mas é um elemento majoritário.

Não nos é dito nada sobre se existe algum tipo de ordenação no tipo de elemento, embora, obviamente, devamos ser capazes de comparar dois por igualdade.

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

Complexidade do Tempo 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/2) { System.out.println("majority element"+arr[i]); break; } } } 

}

Uma versão modificada do Algoritmo de Boyer,

  • 3 passagens onde
    • Na primeira passagem, fazemos uma iteração do array
    • Na segunda passagem, fazemos uma iteração reversa da matriz.
    • Em terceiro passe, obtenha contagens para os elementos maioritários obtidos no primeiro e segundo passes.

Tecnicamente, um algoritmo de complexidade linear (O (3n)). Eu acredito que isso deve funcionar para um array com um elemento majoritário que ocorre pelo menos n / 2 vezes.

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

Código testado aqui

Obrigado pelas respostas anteriores, que me inspirou a saber algo de Bob Boyer. 🙂

Versão genérica Java: Uma versão modificada do Algoritmo de Boyer

Nota: a matriz do tipo primitivo pode usar o 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(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(); } 

}

// Suponha que nos seja dado um array A. // Se tivermos todos os elementos no array dado, cada elemento é menor que K, então podemos criar um array B adicional com comprimento K + 1.

// Inicialize o valor em cada índice da matriz com 0. // Então itere através da matriz dada A, para cada valor da matriz A [i], incremente o valor com 1 no índice correspondente A [i] na matriz criada B.

// Após iterar pelo array A, agora percorra o array B e encontre o valor máximo. Se você encontrar o valor maior que n / 2, retorne esse índice específico.

// Time Complexity será O (n + K) se K <= n então equivalente a O (n).

// Nós temos uma restrição aqui que todos os elementos da matriz são O (K). // Supondo que cada elemento seja menor ou igual a 100, neste caso, K é 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)); } } 

Isso ajudará você e se dois elementos repetirem o mesmo número de vezes se não mostrarem nenhum.

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

É assim que faço em C ++ usando vetor e multimap (JSON com chaves de repetição).

 #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 

Classifique a matriz dada: O (nlogn).

Se o tamanho da matriz for 7, o elemento majoritário ocorrerá pelo menos no teto (7/2) = 4 vezes na matriz.

Depois que o array é classificado, significa que se o elemento majoritário for encontrado pela primeira vez na posição i, ele também será encontrado na posição i + floor (7/2) (4 ocorrências).

Exemplo – dado array A – {7,3,2,3,3,6,3}

Classifique o array – {2,3,3,3,3,6,7}

O elemento 3 é encontrado na posição 1 (índice de matriz a partir de 0.) Se a posição 1 + 3 = 4º elemento também é 3, então significa que 3 é o elemento maioritário.

se passamos pelo array desde o começo ..

compare a posição 0 com a posição 3, os diferentes elementos 2 e 3. compare a posição 1 com a posição 4, mesmo elemento. Encontramos o nosso maior número!

Complexidade – O (n)

Complexidade total do tempo – O (n).