Encontre a entrada mais comum em uma matriz

Question

é-lhe dada uma matriz de números inteiros sem sinal de 32 bits com um comprimento de até 2 ³² , com a propriedade de que mais de metade das entradas na matriz são igual a N, cerca de 32 bits unsigned N. inteiro Encontre N olhando para cada número na matriz apenas uma vez e usando no máximo 2 kB de memória.

A sua solução deve ser determinista, e garantido para encontrar N.

Answer 1

Manter um número inteiro para cada bit, e incrementar esta colecção de forma adequada para cada número inteiro na matriz.

No final, alguns dos bits terá uma contagem maior do que metade do comprimento da matriz de - determinar os bits N. Claro que, a contagem será maior do que o número de vezes N ocorreram, mas que não faz importam. O importante é que qualquer bit, que não faz parte do N não pode ocorrer mais de metade das vezes (porque N tem mais de metade das entradas) e qualquer bit que faz parte do N deve ocorrer mais de metade das vezes (porque ele vai ocorrer cada vez N ocorre e nenhum extras).

(sem código no momento -. Prestes a perder o acesso à rede Esperemos que o acima é clara o suficiente embora.)

Answer 2

Boyer e "Time Linear Maioria Vote Algorithm" de Moore - ir para baixo a matriz mantendo seu palpite atual com a resposta.

Answer 3

Você pode fazer isso com apenas duas variáveis.

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

Faça o primeiro número o número suspeito, e continuar loop através da lista. Se o número de jogos, aumentar a força por uma suspeita; se ele não corresponder, diminuir a força suspeita por um. Se a força suspeita atinge 0 o número atual se torna o suspeito número. Esta vontade não trabalho para encontrar o número mais comum, apenas um número que é mais do que 50% do grupo. Resista à tentação de adicionar uma verificação se suspicionStrength é maior do que a metade do comprimento lista -. Que sempre resultará em comparações mais totais

P.S. Eu não testei este código -. Usá-lo em seu próprio perigo

Answer 4

código Pseudo (notepad C ++ :-)) para o 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, se o a0, a1, . . . , an−1 sequência contém um líder, em seguida, depois de retirar um par de elementos de diferentes valores, a sequência restante ainda tem o mesmo líder. Na verdade, se nós remover dois elementos diferentes, em seguida, apenas um deles poderia ser o líder. O líder na nova sequência ocorre mais do que n/2 − 1 = (n−2)/2 vezes. Consequentemente, ainda é o líder do nova sequência de elementos n − 2.

Aqui está uma implementação Python, com O complexidade (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 é um problema padrão em streaming de algoritmos (onde você tem um enorme fluxo (potencialmente infinita) de dados) e você tem que calcular algumas estatísticas deste fluxo, passando por esta corrente uma vez.

---

É claro que você pode abordá-lo com hash ou classificação, mas com fluxo potencialmente infinito você claramente ficar sem memória. Então você tem que fazer algo inteligente aqui.

---

O elemento maioria é o elemento que ocorre mais do que metade do tamanho da matriz . Isto significa que o elemento maioria ocorre mais do que todos os outros elementos combinados ou se você contar o número de vezes, aparece elemento da maioria, e subtrair o número de todos os outros elementos, você vai ter um número positivo.

Então, se você contar o número de algum elemento, e subtrair o número de todos os outros elementos e obter o número 0 - então o seu elemento original não pode ser um elemento de maioria. Isto se a base para um algoritmo correto:

tem duas variáveis, balcão e possível elemento. Iterate o fluxo, se o contador é 0 - seu sobrescrever a possível elemento e inicializar o contador, se o número é o mesmo que possível elemento - aumentar o contador, caso contrário, reduzi-lo 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 para ver que o algoritmo é O(n) com uma pequena constante antes O(n) (como 3). Também parece que a complexidade espaço é O(1), porque temos apenas três variável inicializada. O problema é que uma destas variáveis ??é um contador que, potencialmente, podem crescer até n (quando a matriz é constituído pelos mesmos números). E para armazenar a n número que você precisa de espaço O(log (n)). Então a partir do ponto de vista teórico é hora O(n) e espaço O(log(n)). De prático , você pode caber 2 ^ 128 número em um inteiro longo e este número de elementos na matriz é inimaginavelmente grande.

Além disso, note que o algoritmo funciona somente se houver um elemento de maioria. Se tal elemento não existe ainda vai voltar algum número, que será certamente errado. (É fácil de modificar o algoritmo para dizer se o elemento maioria existe)

canal

História: este algoritmo foi inventado em algum lugar em 1982 por Boyer, Moore e chamou Boyer-Moore algoritmo maioria .

Answer 7

Eu tenho recordações deste algoritmo, que pode ou não seguir a regra 2K. Ele pode precisar ser reescrito com pilhas e similares para evitar quebrar os limites de memória devido a chamadas de função, mas isso pode ser desnecessário, uma vez que só já tem um número logarítmica de tais chamadas. De qualquer forma, eu tenho lembranças vagas de faculdade ou uma solução recursiva para esta que divide os envolvidos e conquistar, o ser segredo que quando você divide os grupos pela metade, pelo menos, uma das metades ainda tem mais da metade de seus valores igual ao máximo . A regra básica ao dividir é que você retornar dois valores principais candidatos, um dos quais é o valor superior e um dos quais é algum outro valor (que podem ou não ser 2º lugar). I esquecer o algoritmo em si.

Answer 8

prova de correção para buti-oxa / resposta de Jason Hernandez, assumindo a resposta de Jason é o mesmo que a resposta de buti-oxa e ambos trabalham a forma como o algoritmo descrito deve funcionar:

Definimos ajustado força suspeita como sendo igual à força suspeita se o valor superior é selecionado ou -suspicion força se o valor superior não está marcada. Toda vez que você pegar o número certo, a força suspeita corrente aumenta ajustados por 1. Cada vez que você escolhe um número errado, ou ele cai por 1 ou aumenta em 1, dependendo se o número errado está selecionado no momento. Então, o mínimo possível acabar com a força suspeita ajustado é igual ao número de valores [topo] - número de [outros valores]