Elemento majoritário com c ++

Seja n o número de elementos em um vetor ou matriz. O elemento majoritário ou líder é o elemento que ocorre mais da metade das vezes de todos os elementos do vetor. Metade de N significa: se n é 10, então metade do tempo é 5. O elemento na metade da posição está no índice 4, para contagem de índice baseado em zero. O menor número inteiro que é mais da metade de 10 é claramente 6 (correspondente ao índice 5). Se n é 11, então metade de n é considerada ainda como 5. Este é o número inteiro retirado quando 11 é dividido por 2. O índice para metade ainda é de 4 para indexação baseada em zero. Quando n é 11, o menos inteiro que é claramente mais do que a metade literal de 11 ainda é 6 (correspondente ao índice 5).

Portanto, metade do comprimento (tamanho) de um vetor é o resultado da divisão inteira de n por 2. Isto é, todo o número do quociente, depois de dividir por 2, é tomado se há ou não um restante.

O elemento majoritário ou líder é o elemento que ocorre mais da metade das vezes de todos os elementos do vetor ou matriz. Deve ser mais da metade das vezes e não apenas metade das vezes. Isto é, deve ser mais de N/2 vezes (levando o número inteiro resultante). A função deve retornar -1, se não houver elemento majoritário.

Este artigo explica como determinar o elemento majoritário para uma complexidade do tempo de O (n). Ou seja, é necessário um máximo de n operações principais para obter o elemento majoritário.

Exemplos de vetores

Considere o seguinte vetor:

vetor A = 6, 8, 4, 6, 8, 6, 6

O elemento majoritário (líder) é 6. Ocorre 4 vezes em 7 vezes (elementos).

Considere o seguinte vetor:

vetor B = 3, 4, 3, 2, 3, -1, 3, 3

O elemento majoritário é 3. Ocorre 5 vezes em 8 elementos.

Considere o seguinte vetor:

vetor C = 4, 3, 4, 4, 4, 2

O elemento majoritário é 4. Ocorre 4 vezes em 6 elementos.

Considere o seguinte vetor:

vetor D = 5, 4, 7, 1, 7, 2, 3, 7, 8

Não há elemento majoritário aqui. Então, a função tem que retornar -1. Existem nove elementos aqui. O número, 7, ocorre três vezes e cada um dos outros elementos ocorrem uma vez. Três não são mais da metade dos nove. Um elemento majoritário aceitável deveria ter ocorrido, pelo menos 5 vezes.

Ilustração para algoritmo para a (n) complexidade do tempo

A partir dos seguintes vetores, dois elementos diferentes são removidos ao mesmo tempo.

Considere novamente o vetor:

vetor A = 6, 8, 4, 6, 8, 6, 6

O elemento líder (maioria) é 6. Os dois primeiros elementos são diferentes. Se os dois forem removidos, o conjunto restante seria, 4, 6, 8, 6, 6. Neste conjunto restante, 6 ainda é o líder: três vezes em 5 vezes. Os próximos dois elementos, 4 e 6 são diferentes. Se eles forem removidos, o conjunto restante será 8, 6, 6. No conjunto restante, 6 ainda é o líder. Os próximos dois elementos, 8 e 6 são diferentes. Se eles forem removidos, o conjunto restante será 6. Neste último conjunto de apenas um elemento, 6 ainda é o líder. Portanto, parece que dois números diferentes são removidos repetidamente. O elemento restante final seria o elemento majoritário.

Considere agora o vetor:

vetor B = 3, 4, 3, 2, 3, -1, 3, 3

O elemento líder (maioria) é 3. Os dois primeiros elementos são diferentes. Se os dois forem removidos, o conjunto restante seria, 3, 2, 3, -1, 3, 3. Neste conjunto restante, 3 ainda é o líder: quatro vezes em seis vezes. Os próximos dois elementos, 3 e 2 são diferentes. Se eles forem removidos, o conjunto restante será 3, -1, 3, 3. No conjunto restante, 3 ainda é o líder. Os próximos dois elementos, 3 e -1 são diferentes. Se eles forem removidos, o conjunto restante será 3, 3. Neste último conjunto de dois elementos, 3 ainda é o líder. Portanto, ainda parece que dois números diferentes são removidos repetidamente. Os mesmos elementos restantes finais seriam o elemento majoritário.

Considere a seguir o vetor:

vetor C = 4, 3, 4, 4, 4, 2

O elemento líder (maioria) é 4. Os dois primeiros elementos são diferentes. Se os dois forem removidos, o conjunto restante seria, 4, 4, 4, 2. Neste conjunto restante, 4 ainda é o líder: três vezes em quatro vezes. Os próximos dois elementos, 4 e 4 são os mesmos e não devem ser removidos. No entanto, o primeiro elemento aqui e o terceiro elemento aqui pode ser considerado para remoção. Acontece que esses dois também são iguais. Ainda assim, o primeiro elemento e o quarto elemento podem ser considerados para remoção. Eles são diferentes, então são removidos. O último conjunto restante é 4, 4. Portanto, ainda parece que dois números diferentes são removidos repetidamente. Os mesmos elementos restantes restantes seriam o elemento majoritário.

Considere então o vetor:

vetor D = 5, 4, 7, 1, 7, 2, 3, 7, 8

Já sabemos que esse vetor não tem líder, embora 7 ocorram três vezes e o número do outro ocorra uma vez. 7 ocorre três em cada nove vezes e isso não o torna um líder. Ainda assim, pares diferentes podem ser removidos repetidamente para ver como seria o conjunto restante final. Os dois primeiros elementos, 5 e 4 são diferentes. Se eles forem removidos, o conjunto restante seria, 7, 1, 7, 2, 3, 7, 8. Neste conjunto restante, 7 ainda é o elemento predominante. Mas ainda não é o líder do conjunto restante. Lembre -se de que o líder deve ocorrer mais da metade do número de vezes. Os próximos dois elementos, 7 e 1 são diferentes. Se eles forem removidos, o conjunto restante seria 7, 2, 3, 7, 8. 7 ainda é o elemento predominante, mas ainda não é o líder. Os próximos dois elementos, 7 e 2 são diferentes. Eles são removidos para ter o conjunto, 3, 7, 8. Não há elemento predominante restante desta vez e não há líder. Os próximos dois elementos, 3 e 7 são diferentes. Quando eles são removidos, o conjunto restante seria 8.

Para os três vetores anteriores, o elemento final restante ou o mesmo elementos finais restantes é o elemento majoritário. Já se sabe que não existe a maioria (líder) elemento neste último vetor. Portanto, o fato de um elemento finalmente permanecer não significa necessariamente que é o elemento majoritário.

Agora, considere o caso em que n é um número par e cada elemento no vetor ocorre uma vez. Nesse caso, todos os pares de elementos serão removidos e não haverá nenhum elemento no conjunto final. Claramente, neste caso, a função deve retornar -1, pois não há elemento majoritário.

Para o final restante, um elemento ou o mesmo elementos restantes deve ser verificado se o elemento ocorre mais da metade do número de vezes no vetor. Este elemento restante é chamado de candidato.

O (n) Algoritmo de complexidade do tempo para o elemento majoritário

A estratégia é remover pares de elementos diferentes, repetidamente: começando da esquerda no vetor dado. Se nenhum elemento permanecer, não há elemento majoritário e a função deve retornar -1. Se um ou mais dos mesmos elementos permanecem, deve ser verificado se o elemento ocorre mais da metade dos tempos no vetor. Este elemento é chamado de candidato. Torna -se o elemento majoritário se ocorrer mais da metade do número de vezes.

Essa verificação pode ser feita em tempo linear, digitalizando o vetor da esquerda e para parar assim que o número de ocorrência for apenas maior que a metade do comprimento do vetor. Se todo o vetor for digitalizado e o número de vezes que o candidato ocorre não é superior à metade dos tempos, então não há elemento majoritário (de acordo com a definição).

Estratégia com c++

Com C ++, os elementos não precisam ser removidos do vetor determinado. Em vez disso, uma pilha é usada. O primeiro elemento do vetor é empurrado para o topo da pilha. Se o próximo elemento for diferente do elemento superior na pilha, o elemento superior na pilha será removido (apareceu); Caso contrário, este próximo elemento será empurrado para o topo da pilha (se o elemento superior da pilha e o próximo elemento, são os mesmos). Este esquema continua para o resto dos elementos.

No final da digitalização (um passe do vetor), se nenhum elemento estiver na pilha, não há elemento majoritário. Um ou mais elementos podem permanecer na pilha. Se mais de um elemento permanecer na pilha, esses elementos restantes devem ser iguais. Este elemento é chamado de candidato.

Se um ou mais do mesmo elemento permanecem na pilha, esse elemento ou o mesmo elemento que ocorre mais de uma vez é um possível elemento majoritário. O vetor deve ser escaneado para ver se esse elemento ocorre mais da metade do número de vezes para o número total de elementos no vetor. Se ocorrer mais da metade dos tempos, esse elemento é o elemento da maioria (líder); Caso contrário, o vetor (ou matriz) não tem elemento majoritário (a função deve retornar -1).

Codificação C ++

Sempre que um vetor é usado em um programa C ++, o título do programa deve ser algo como:

#incluir
#incluir
#incluir
usando namespace std;

A biblioteca de pilhas deve ser incluída. O namespace padrão é usado. O vetor é a lista principal, então sua biblioteca está incluída. A biblioteca iostream sempre deve ser incluída; é responsável pela entrada/saída. O nome da função para o algoritmo O (n) é MaiorityElement. A primeira metade do código da função é:

Int MaiorityElement (vetor &A)
int n = a.tamanho();
int tamanho = 0;
pilha ST;
st.push (a [0]);
para (int i = 1; iif (st.tamanho ()> 0) // para evitar, falha de segmentação (dumped) erro
if (a [i] == st.principal())
st.push (a [i]);

outro
st.pop (); //se diferente


outro
st.push (a [i]); // empurre para o topo da pilha se vazio

Este tem o primeiro loop para o loop principal. Antes do loop for, o primeiro elemento do vetor é enviado para a pilha (a parte superior). Isso implementa para o loop que a estratégia C ++ é mencionada acima. A segunda e a última parte da função MaiorityElement () é:

int candidato = -1;
if (st.tamanho ()> 0)
candidato = st.principal();
int líder = -1;
int conting = 0;
para (int i = 0; iif (a [i] == candidato)
contagem += 1;


se (contagem> n/2)
líder = candidato;
líder de retorno;

Isso verifica se o candidato é realmente o elemento majoritário. O líder variável é um sinônimo do elemento majoritário. O candidato variável é o possível elemento majoritário. Assim que o valor da contagem exceder N/2, o candidato é o elemento majoritário. Esta parte tem o loop for que verifica se o vetor tem um elemento majoritário. As duas partes acima devem ser unidas para formar uma função. A função retorna -1, se não houver elemento majoritário.

Uma função principal C ++ adequada, para o código acima é:

vetor v1 = 6, 8, 4, 6, 8, 6, 6;
int ret1 = majorityElement (v1);
cout << ret1 << endl;
vetor v2 = 3, 4, 3, 2, 3, -1, 3, 3;
int ret2 = majorityElement (v2);
cout << ret2 << endl;
vetor v3 = 4, 3, 4, 4, 4, 2;
int ret3 = majorityElement (v3);
cout << ret3 << endl;
vetor v4 = 5, 4, 7, 1, 7, 2, 3, 7, 8;
int ret4 = majorityElement (v4);
cout << ret4 << endl;
retornar 0;

Complexidade do tempo

Como existem dois loops com o vetor sendo digitalizado duas vezes, o leitor pode ser tentado a dizer que a complexidade do tempo é: O (n+n). Agora, o corpo do primeiro loop é muito mais longo que o corpo para o segundo loop para. Portanto, o tempo para o segundo corpo de circuito executar é muito menor que o tempo para o primeiro corpo do loop executar. Em outras palavras, esse tempo para o segundo corpo é relativamente insignificante. Portanto, a complexidade do tempo para o algoritmo acima é citada como:

Sobre)

A complexidade do tempo é o número aproximado de operações principais para a função em questão.

Conclusão

A estratégia geral para encontrar o elemento majoritário no tempo de O (n) deve estar removendo pares de elementos que são diferentes, repetidamente, começando da esquerda na lista dada. Se nenhum elemento permanecer, finalmente na lista, não há elemento majoritário e a função deve retornar -1. Se um ou mais do mesmo elemento permanecerem, deve ser verificado se o elemento ocorrer mais da metade dos tempos da lista. Este elemento é chamado de candidato. Se o candidato ocorrer mais da metade dos tempos, na lista fornecida, o candidato é o elemento majoritário.

Chrys