Encuentra la entrada más común en una matriz

Question

Se le proporciona una matriz entera sin signo de 32 bits con una longitud de hasta 2 ³² , con la propiedad de que más de la mitad de las entradas en la matriz son iguales a N, para algunos de 32 bits entero sin signo N. Busque N mirando cada número de la matriz solo una vez y utilizando como máximo 2 kB de memoria.

Su solución debe ser determinista y garantizar que encuentre N.

Answer 1

Mantenga un número entero para cada bit e incremente esta colección de manera apropiada para cada número entero en la matriz.

Al final, algunos de los bits tendrán un recuento superior a la mitad de la longitud de la matriz; esos bits determinan N. Por supuesto, el recuento será mayor que la cantidad de veces que se produjo N, pero eso no importar. Lo importante es que cualquier bit que no sea parte de N no puede ocurrir más de la mitad de las veces (porque N tiene más de la mitad de las entradas) y cualquier bit que sea parte de N debe ocurre más de la mitad de las veces (porque ocurrirá cada vez que ocurra N y cualquier extra).

(No hay código en este momento, a punto de perder el acceso a la red. Sin embargo, espero que lo anterior sea lo suficientemente claro).

Answer 2

Boyer y Moore " Algoritmo de voto de mayoría de tiempo lineal " ; : baje la matriz manteniendo su respuesta actual a la respuesta.

Answer 3

Puede hacer esto con solo dos variables.

public uint MostCommon(UInt32[] numberList)
{
    uint suspect = 0;
    int suspicionStrength = -1; 
    foreach (uint number in numberList)
    {
        if (number==suspect)
        {
            suspicionStrength++;
        }
        else
        {
            suspicionStrength--;
        }

        if (suspicionStrength<=0)
        {
            suspect = number;
        }
    }
    return suspect;
}

Convierta el primer número en el número sospechoso y continúe recorriendo la lista. Si el número coincide, aumente la fuerza de sospecha en uno; Si no coincide, reduzca la fuerza de sospecha en uno. Si la fuerza de la sospecha llega a 0, el número actual se convierte en el número sospechoso. Esto no funcionará para encontrar el número más común, solo un número que es más del 50% del grupo. Resista el impulso de agregar una comprobación si suspicionStrength es mayor que la mitad de la longitud de la lista; siempre dará como resultado más comparaciones totales.

P.S. No he probado este código, úselo bajo su propio riesgo.

Answer 4

Pseudocódigo (bloc de notas C ++ :-)) para el algoritmo de Jon:

int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);

for (int i = 0; i < lNumbers; i++)
  for (int bi = 0; bi < 32; bi++)
    arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;

int N = 0;

for (int bc = 0; bc < 32; bc++)
  if (arrBits[bc] > lNumbers/2)
    N = N | (1 << bc);

Answer 5

Observe que si la secuencia a0, a1,. . . , un - 1 contiene un líder, luego de eliminar un par de elementos de diferentes valores, la secuencia restante todavía tiene el mismo líder. De hecho, si nosotros eliminar dos elementos diferentes, entonces solo uno de ellos podría ser el líder. El líder en el la nueva secuencia ocurre más de n / 2 - 1 = (n - 2) / 2 veces. En consecuencia, sigue siendo el líder de la nueva secuencia de elementos n - 2 .

Aquí hay una implementación de Python, con complejidad de tiempo O (n):

def goldenLeader(A):
    n = len(A)
    size = 0
    for k in xrange(n):
        if (size == 0):
            size += 1
            value = A[k]
        else:
            if (value != A[k]):
                size -= 1
            else:
                size += 1
    candidate = -1
    if (size > 0):
        candidate = value
    leader = -1
    count = 0
    for k in xrange(n):
        if (A[k] == candidate):
            count += 1
    if (count > n // 2):
        leader = candidate
    return leader

Answer 6

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 u ordenamiento, pero con una transmisión potencialmente infinita, se queda sin memoria. Entonces tienes que hacer algo inteligente aquí.

---

El elemento mayoritario es el elemento que ocurre más de la mitad del tamaño de la matriz . Esto significa que el elemento mayoritario ocurre más que todos los demás elementos combinados o si cuenta el número de veces, aparece el elemento mayoritario y resta el número de todos los demás elementos, obtendrá un número positivo.

Entonces, si cuenta el número de algún elemento y resta el número de todos los demás elementos y obtiene el número 0, entonces su elemento original no puede ser un elemento mayoritario. Esto si la base para un algoritmo correcto:

Tiene dos variables, contador y posible elemento. Itere la secuencia, si el contador es 0 - sobrescribe el elemento posible e inicializa el contador, si el número es el mismo que el elemento posible - aumente el contador, de lo contrario disminuya. Código de 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

Está claro que el algoritmo es O (n) con una constante muy pequeña antes de 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 la matriz consta de los mismos números). Y para almacenar el número n necesita espacio O (log (n)) . Entonces, desde el punto de vista teórico es O (n) tiempo y O (log (n)) espacio. Desde la práctica , puede caber un número 2 ^ 128 en una entrada larga y este número de elementos en la matriz es inimaginablemente grande.

También tenga en cuenta que el algoritmo funciona solo si hay un elemento mayoritario. Si dicho elemento no existe, devolverá algún número, lo que seguramente será incorrecto. (es fácil modificar el algoritmo para saber si existe el elemento mayoritario)

Canal de historia: Boyer, Moore inventó este algoritmo en 1982 y lo llamó Boyer & # 8211; algoritmo de voto mayoritario de Moore .

Answer 7

Tengo recuerdos de este algoritmo, que podría o no seguir la regla 2K. Es posible que deba reescribirse con pilas y similares para evitar romper los límites de memoria debido a las llamadas a funciones, pero esto puede ser innecesario ya que solo tiene un número logarítmico de tales llamadas. De todos modos, tengo vagos recuerdos de la universidad o una solución recursiva a esto que implicó dividir y conquistar, el secreto es que cuando divide los grupos por la mitad, al menos una de las mitades aún tiene más de la mitad de sus valores iguales al máximo . La regla básica al dividir es que devuelve dos valores superiores candidatos, uno de los cuales es el valor superior y uno de los cuales es algún otro valor (que puede ser o no el segundo lugar). Olvidé el algoritmo mismo.

Answer 8

Prueba de corrección para la respuesta de buti-oxa / Jason Hernández, suponiendo que la respuesta de Jason sea la misma que la respuesta de buti-oxa y que ambas funcionen de la manera en que debería funcionar el algoritmo descrito:

Definimos la fuerza de sospecha ajustada como igual a la fuerza de sospecha si se selecciona el valor superior o la fuerza de sospecha si no se selecciona el valor superior. Cada vez que elige el número correcto, la intensidad de sospecha ajustada actual aumenta en 1. Cada vez que elige un número incorrecto, disminuye en 1 o aumenta en 1, dependiendo de si el número incorrecto está seleccionado actualmente. Por lo tanto, la fuerza de sospecha ajustada final mínima posible es igual al número de [valores superiores] - número de [otros valores]