Sugerir um algoritmo eficiente

Question

Dada uma matriz arr do tamanho 100000, cada elemento 0 <= arr[i] < 100. (não classificado, contém duplicatas)

Descubra quantos trigêmeos (i,j,k) estão presentes de modo que arr[i] ^ arr[j] ^ arr[k] == 0 Observação : ^ é o operador XOR. também 0 <= i <= j <= k <= 100000

Tenho a sensação de que tenho que calcular as frequências e fazer algum cálculo usando a frequência, mas simplesmente não consigo começar.

Qualquer algoritmo melhor do que o óbvio O(n^3) é bem -vindo. :)

Não é lição de casa. :)

Answer 1

Eu acho que a chave é que você não precisa identificar o i, j, k, apenas conte quantas.

Inicialize uma matriz tamanho 100

Loop embora arr, contando quantos de cada valor existem - o (n)

Loop através de elementos diferentes de zero da pequena matriz, calculando o que os triplos atendem à condição - suponha )/!ABC! - 100 ** 3 operações, mas isso ainda é O (1) assumindo que o 100 seja um valor fixo.

Em breve).

Answer 2

Solução possível (n^2), se funcionar: manter a variável count e duas matrizes, single[100] e pair[100]. Itera o arr, e para cada elemento de valor n:

• atualizar count: count += pair[n]
• atualizar pair: itera matriz single e para cada elemento do índice x e valor s != 0 Faz pair[s^n] += single[x]
• atualizar single: single[n]++

No fim count mantém o resultado.

Answer 3

Solução possível O (100 * n) = O (n). resolve o problema i <= j <= k. Como você conhece a ^ b = 0 <=> a = b, então

long long calcTripletsCount( const vector<int>& sourceArray )
{
  long long res = 0;
  vector<int> count(128);
  vector<int> countPairs(128);
  for(int i = 0; i < sourceArray.size(); i++)
  {
    count[sourceArray[i]]++; // count[t] contain count of element t in (sourceArray[0]..sourceArray[i]) 
    for(int j = 0; j < count.size(); j++)
      countPairs[j ^ sourceArray[i]] += count[j]; // countPairs[t] contain count of pairs p1, p2 (p1 <= p2 for keeping order) where t = sourceArray[i] ^ sourceArray[j]
    res += countPairs[sourceArray[i]]; // a ^ b ^ c = 0 if a ^ b = c, we add count of pairs (p1, p2) where sourceArray[p1] ^ sourceArray[p2] = sourceArray[i]. it easy to see that we keep order(p1 <= p2 <= i)
  }  
  return res;
}

Desculpe pelo meu inglês ruim ...

Answer 4

Eu tenho uma solução (simples) o (n^2 log n) que leva em consideração o fato de que eu, j e k me referem a índices, não inteiros.

Uma primeira passagem simples nos permite criar uma matriz A de 100 valores: valores -> Lista de índices, mantemos a lista classificada para uso posterior. O (n log n)

Para cada par i, j tal que i <= j, nós calculamos x = arr [i]^arr [j]. Em seguida, realizamos uma pesquisa binária em um [x] para localizar o número de índices k de modo que k> = j. O (n^2 log n)

Não consegui encontrar nenhuma maneira de aproveitar o algoritmo de classificação / contagem de classificação porque eles aniquilarem o requisito do índice.

Answer 5

Sort the array, keeping a map of new indices to originals. O(nlgn)
Loop over i,j:i<j. O(n^2)
  Calculate x = arr[i] ^ arr[j]
  Since x ^ arr[k] == 0, arr[k] = x, so binary search k>j for x. O(lgn)
  For all found k, print mapped i,j,k

O (n^2 lgn)

Answer 6

Comece com uma contagem de frequência do número de ocorrências de cada número entre 1 e 100, como sugere Paulo. Isso produz uma matriz freq [] de comprimento 100.

Em seguida, em vez de loop sobre triplos A, B, C dessa matriz e testar a condição a^b^c = 0, loop sobre os pares a, b com A <B. para cada a, b, calcule C = a^B (para que agora a^b^c = 0) e verifique se a <b <c <100. (qualquer triplo ocorrerá em alguma ordem, para que isso não perca triplos. Mas veja abaixo). O total de corrida será:

Sum+=freq[A]*freq[B]*freq[C]

O trabalho é O (n) para a contagem de frequência, além de cerca de 5000 para o loop sobre A <B.

Já que cada triplo de três diferente Os números A, B, C devem ocorrer em alguma ordem, isso encontra cada um desses triplos exatamente uma vez. Em seguida, você terá que procurar triplos nos quais dois números são iguais. Mas se dois números forem iguais e o XOR de três é 0, o terceiro número deve ser zero. Portanto, isso equivale a uma pesquisa linear secundária por B sobre a matriz de contagem de frequência, contando ocorrências de (a = 0, b = c <100). (Tenha muito cuidado com este caso, e especialmente cuidadoso com o caso B = 0. A contagem não é apenas Freq [B] ** 2 ou Freq [0] ** 3. Há um pequeno problema de combinatória escondido lá.)

Espero que isto ajude!