Elemento mayoritario con c ++

Sea n el número de elementos en un vector o matriz. El elemento o líder de la mayoría es el elemento que ocurre más de la mitad de los tiempos de todos los elementos en el vector. La mitad de n significa: si n es 10, entonces la mitad del tiempo es 5. El elemento en la mitad de la posición está en el índice 4, para contar índice basado en cero. El menor entero que es más de la mitad de 10 es claramente 6 (correspondiente al índice 5). Si n es 11, entonces la mitad de n se considera aún como 5. Este es el número completo tomado cuando 11 se divide por 2. El índice para la mitad sigue siendo 4 para la indexación basada en cero. Cuando n es 11, el menor entero que es claramente más que la mitad literal de 11 sigue siendo 6 (correspondiente al índice 5).

Entonces, la mitad de la longitud (tamaño) de un vector es el resultado de la división entera de N por 2. Es decir, el número completo del cociente, después de dividirse por 2, se toma si hay un resto o no.

El elemento o líder de la mayoría es el elemento que ocurre más de la mitad de los tiempos de todos los elementos en el vector o matriz. Debe ser más que la mitad de los tiempos y no solo la mitad de los tiempos. Es decir, debe ser más de n/2 veces (tomando el número completo resultante). La función debe devolver -1, si no existe ningún elemento mayoritario.

Este artículo explica cómo determinar el elemento mayoritario para una complejidad de tiempo de O (n). Es decir, se necesita un máximo de las operaciones principales de N para obtener el elemento mayoritario.

Ejemplos de vector

Considere el siguiente vector:

vector A = 6, 8, 4, 6, 8, 6, 6

El elemento mayoritario (líder) es 6. Ocurre 4 veces de 7 veces (elementos).

Considere el siguiente vector:

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

El elemento mayoritario es 3. Ocurre 5 veces de 8 elementos.

Considere el siguiente vector:

vector C = 4, 3, 4, 4, 4, 2

El elemento mayoritario es 4. Ocurre 4 veces de 6 elementos.

Considere el siguiente vector:

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

No hay elemento mayoritario aquí. Entonces, la función tiene que devolver -1. Hay nueve elementos aquí. El número, 7, ocurre tres veces y cada uno de los otros elementos ocurre una vez. Tres no son más de la mitad de nueve. Debería haber ocurrido un elemento mayoritario aceptable, al menos 5 veces.

Ilustración para el algoritmo para O (n) complejidad del tiempo

De los siguientes vectores, se eliminan dos elementos diferentes al mismo tiempo.

Considere nuevamente el vector:

vector A = 6, 8, 4, 6, 8, 6, 6

El elemento líder (mayoría) es 6. Los primeros dos elementos son diferentes. Si ambos se eliminan, el conjunto restante sería, 4, 6, 8, 6, 6. En este set restante, 6 sigue siendo el líder: tres veces de 5 veces. Los siguientes dos elementos, 4 y 6 son diferentes. Si se eliminan, el conjunto restante será 8, 6, 6. En el set restante, 6 sigue siendo el líder. Los siguientes dos elementos, 8 y 6 son diferentes. Si se eliminan, el conjunto restante será 6. En este último conjunto de un solo elemento, 6 sigue siendo el líder. Por lo tanto, parece que dos números diferentes se eliminan repetidamente. El elemento final restante sería el elemento mayoritario.

Considere ahora el vector:

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

El elemento líder (mayoría) es 3. Los primeros dos elementos son diferentes. Si ambos se eliminan, el conjunto restante sería, 3, 2, 3, -1, 3, 3. En este set restante, 3 sigue siendo el líder: cuatro de cada seis veces. Los siguientes dos elementos, 3 y 2 son diferentes. Si se eliminan, el conjunto restante será 3, -1, 3, 3. En el set restante, 3 sigue siendo el líder. Los siguientes dos elementos, 3 y -1 son diferentes. Si se eliminan, el conjunto restante será 3, 3. En este último conjunto de dos elementos, 3 sigue siendo el líder. Por lo tanto, todavía parece que dos números diferentes se eliminan repetidamente. Los mismos elementos restantes finales serían el elemento mayoritario.

Considere a continuación el vector:

vector C = 4, 3, 4, 4, 4, 2

El elemento líder (mayoría) es 4. Los primeros dos elementos son diferentes. Si ambos se eliminan, el conjunto restante sería, 4, 4, 4, 2. En este set restante, 4 sigue siendo el líder: tres veces de cuatro veces. Los siguientes dos elementos, 4 y 4 son los mismos y no deben eliminarse. Sin embargo, el primer elemento aquí, y el tercer elemento aquí, se puede considerar para la eliminación. Sucede que estos dos también son los mismos. Aún así, el primer elemento y el cuarto elemento pueden considerarse para la eliminación. Son diferentes, por lo que se eliminan. El último conjunto restante es 4, 4. Por lo tanto, todavía parece que dos números diferentes se eliminan repetidamente. Los mismos elementos finales restantes serían el elemento mayoritario.

Considere entonces el vector:

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

Ya sabemos que este vector no tiene líder, aunque 7 ocurre tres veces y el número de otro ocurre una vez. 7 ocurre tres de cada nueve veces y eso no lo convierte en un líder. Aún así, se pueden eliminar diferentes pares repetidamente para ver cómo se vería el conjunto final restante. Los dos primeros elementos, 5 y 4 son diferentes. Si se eliminan, el conjunto restante sería, 7, 1, 7, 2, 3, 7, 8. En este conjunto restante, 7 sigue siendo el elemento predominante. Pero todavía no es el líder del set restante. Recuerde que el líder debe ocurrir más de la mitad de la cantidad de veces. Los siguientes dos elementos, 7 y 1 son diferentes. Si se eliminan, el conjunto restante sería 7, 2, 3, 7, 8. 7 sigue siendo el elemento predominante, pero sigue siendo el líder. Los siguientes dos elementos, 7 y 2 son diferentes. Se eliminan para tener el conjunto, 3, 7, 8. Esta vez no hay elemento predominante y no hay líder. Los siguientes dos elementos, 3 y 7 son diferentes. Cuando se eliminan, el conjunto restante sería 8.

Para los tres vectores anteriores, el elemento restante final o el elemento final restante restante es el elemento mayoritario. Ya se sabe que no hay un elemento mayoritario (líder) en este último vector. Entonces, el hecho de que un elemento finalmente permanezca no significa necesariamente que sea el elemento mayoritario.

Ahora, considere el caso donde n es un número uniforme y cada elemento en el vector ocurre una vez. En este caso, se eliminarán todos los pares de elementos y no habrá elemento en el conjunto final. Claramente, en este caso, la función tiene que devolver -1 ya que no hay un elemento mayoritario.

Para el elemento final restante o los mismos elementos restantes restantes, tienen que verificarse/debe verificarse si el elemento ocurre más de la mitad de la cantidad de veces en el vector. Este elemento restante se llama candidato.

O (n) Algoritmo de complejidad de tiempo para el elemento mayoritario

La estrategia es eliminar pares de elementos diferentes, repetidamente: comenzando desde la izquierda en el vector dado. Si no queda ningún elemento, entonces no hay un elemento mayoritario y la función debería devolver -1. Si quedan uno o más de los mismos elementos, entonces debe verificarse si el elemento ocurre más de la mitad de las veces en el vector. Este elemento se llama candidato. Se convierte en el elemento mayoritario si ocurre más de la mitad del número de veces.

Esta verificación se puede hacer en tiempo lineal, escaneando el vector desde la izquierda, y para detenerse tan pronto como el número de ocurrencia sea solo mayor de la mitad de la longitud del vector. Si se escanea todo el vector, y el número de veces que ocurre el candidato no es más de la mitad de las veces, entonces no hay un elemento mayoritario (según la definición).

Estrategia con c++

Con C ++, los elementos no tienen que eliminarse del vector dado. En su lugar, se usa una pila. El primer elemento del vector se empuja en la parte superior de la pila. Si el siguiente elemento es diferente del elemento superior en la pila, entonces se elimina el elemento superior en la pila (aparece); De lo contrario, este siguiente elemento se empuja a la parte superior de la pila (si el elemento superior de la pila y el siguiente elemento es el mismo). Este esquema continúa por el resto de los elementos.

Al final del escaneo (un pase del vector), si no hay ningún elemento en la pila, no hay elemento mayoritario. Uno o más elementos pueden permanecer en la pila. Si queda más de un elemento en la pila, entonces estos elementos restantes tienen que ser los mismos. Este elemento se llama candidato.

Si uno o más del mismo elemento permanecen en la pila, ese elemento o el mismo elemento que ocurre más de una vez es un posible elemento mayoritario. El vector debe volver a escanear para ver si este elemento ocurre más de la mitad del número de veces para el número total de elementos en el vector. Si ocurre más de la mitad de los tiempos, entonces ese elemento es el elemento mayoritario (líder); De lo contrario, el vector (o matriz) no tiene un elemento mayoritario (la función debería devolver -1).

Codificación de C ++

Cada vez que se usa un vector en un programa C ++, el encabezado del programa tiene que ser algo así como:

#incluir
#incluir
#incluir
usando el espacio de nombres STD;

La biblioteca de la pila debe ser incluida. Se utiliza el espacio de nombres estándar. Vector es la lista principal, por lo que su biblioteca está incluida. La biblioteca iostream siempre debe ser incluida; es responsable de la entrada/salida. El nombre de la función para el algoritmo O (n) es mayoritaridad. La primera mitad del código de función es:

int MayorityElement (vector &A)
int n = a.tamaño();
int tamaño = 0;
pila calle;
calle.empuje (a [0]);
para (int i = 1; iif (st.size ()> 0) // Para evitar, falla de segmentación (núcleo arrojado) Error
if (a [i] == st.arriba())
calle.empuje (a [i]);

demás
calle.estallido(); //si es diferente


demás
calle.empuje (a [i]); // empuja a la parte superior de la pila si está vacía

Este tiene el primer bucle for-bucle, que es el bucle principal. Antes del bucle for-bucle, el primer elemento del vector se envía a la pila (la parte superior). Este bucle implementa que la estrategia C ++ se menciona anteriormente. La segunda y última parte de la función MayorityElement () es:

int candidato = -1;
if (st.size ()> 0)
candidato = ST.arriba();
int líder = -1;
int count = 0;
para (int i = 0; iif (a [i] == candidato)
recuento += 1;


if (Count> n/2)
líder = candidato;
líder de regreso;

Esto verifica si el candidato es en realidad el elemento mayoritario. El líder variable es sinónimo del elemento mayoritario. El candidato variable es el posible elemento mayoritario. Tan pronto como el valor para el recuento excede N/2, entonces el candidato es el elemento mayoritario. Esta parte tiene el for-bucle que verifica si el vector tiene un elemento mayoritario. Las dos partes anteriores deben unirse para formar una función. La función devuelve -1, si no existe ningún elemento mayoritario.

Una función principal de C ++ adecuada, para el código anterior es:

vector v1 = 6, 8, 4, 6, 8, 6, 6;
int ret1 = mayorityElement (V1);
cout << ret1 << endl;
vector v2 = 3, 4, 3, 2, 3, -1, 3, 3;
int ret2 = mayorityElement (v2);
cout << ret2 << endl;
vector v3 = 4, 3, 4, 4, 4, 2;
int ret3 = mayorityElement (V3);
cout << ret3 << endl;
vector v4 = 5, 4, 7, 1, 7, 2, 3, 7, 8;
int ret4 = mayorityElement (v4);
cout << ret4 << endl;
regresar 0;

Complejidad del tiempo

Dado que hay dos bucles para el vector que se escanea dos veces, el lector podría verse tentado a decir que la complejidad del tiempo es, o (n+n). Ahora, el cuerpo del primer bucle es mucho más largo que el cuerpo para el segundo bucle. Por lo tanto, el tiempo para que el segundo cuerpo del circuito se ejecute es mucho más pequeño que el momento para que el primer cuerpo de bucle se ejecute. En otras palabras, ese tiempo para el segundo cuerpo es relativamente insignificante. Entonces, la complejidad del tiempo para el algoritmo anterior se cita como:

En)

La complejidad del tiempo es el número aproximado de operaciones principales para la función en cuestión.

Conclusión

La estrategia general para encontrar el elemento mayoritario en el tiempo o (n) es eliminar pares de elementos que son diferentes, repetidamente, comenzando desde la izquierda en la lista dada. Si no queda ningún elemento, finalmente en la lista, entonces no hay un elemento mayoritario y la función debe devolver -1. Si queda uno o más del mismo elemento, entonces debe verificarlo si el elemento ocurre más de la mitad de las veces en la lista. Este elemento se llama candidato. Si el candidato ocurre más de la mitad de las veces, en la lista dada, entonces el candidato es el elemento mayoritario.

Chrys