Este artículo fue analizado por nuestros especialistas para garantizar la veracidad de nuestra esta reseña.
Solución:
// 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;
Es triste ver que en 5 años nadie ha escrito una explicación adecuada para este problema.
Este es un problema estándar en los algoritmos de transmisión (donde tiene un flujo de datos enorme (potencialmente infinito)) y tiene que calcular algunas estadísticas de este flujo, pasando por este flujo una vez.
Claramente, puede abordarlo con hash o clasificación, pero con un flujo potencialmente infinito, claramente puede quedarse sin memoria. Así que tienes que hacer algo inteligente aquí.
El elemento mayoritario es el elemento que se presenta en más de la mitad del tamaño del array. Esto significa que el elemento mayoritario ocurre más que todos los demás elementos combinados. Es decir, si cuenta el número de veces que aparece el elemento mayoritario y resta el número de apariciones de todos los demás elementos, obtendrá un número positivo.
Entonces, si cuenta las ocurrencias de algún elemento y resta el número de ocurrencias de todos los demás elementos y obtiene el número 0, entonces su elemento original no puede ser un elemento mayoritario. Esta es la base para un algoritmo correcto:
Declare dos variables, contador y posible_elemento. Itere la secuencia, si el contador es 0, sobrescriba el elemento posible e inicialice el contador, si el número es el mismo que el elemento posible, aumente el contador, de lo contrario, disminúyalo. código pitón:
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
Es claro ver que el algoritmo es O(n) con una constante muy pequeña antes O(n) (como 3). También parece que la complejidad del espacio es O(1), porque solo tenemos tres variables inicializadas. El problema es que una de estas variables es un contador que potencialmente puede crecer hasta n (cuando el array consta de los mismos números). Y para almacenar el número n necesitas O(log (n)) espacio. Entonces desde el punto de vista teorico está O(n) tiempo y O(log(n)) espacio. De prácticopuede caber 2^128 número en un entero largo y este número de elementos en el array es inimaginablemente enorme.
También tenga en cuenta que el algoritmo funciona solo si hay un elemento mayoritario. Si dicho elemento no existe, aún devolverá algún número, que seguramente será incorrecto. (es fácil modificar el algoritmo para saber si existe el elemento mayoritario)
Canal de historia: este algoritmo fue inventado en algún lugar de 1982 por Boyer, Moore y se denominó algoritmo de voto mayoritario de Boyer-Moore.
El elemento mayoritario (si existe) será también la mediana. Podemos encontrar la mediana en O(n) y luego comprobar que efectivamente es un elemento mayoritario válido en O(n). Más detalles para el enlace de implementación
Reseñas y valoraciones
Ten en cuenta difundir esta división si te fue útil.