Dada una matriz que consta de N enteros, ¿puedes encontrar el valor máximo de xor de dos números en una matriz (ai xor aj)?

1. Método ingenuo: Algoritmo O (n ^ 2)

2. Uso de la estructura de datos Trie
¿¿¿¿Cómo????

PASO 1: Construye un trie con los números dados. Trie debe construirse con cada nodo como un bit del número que comienza la construcción desde el bit más significativo. Esto tomará O (N log N)
PASO 2: sabe que idealmente xor de dos números es máximo cuando invierte todos los bits en el número.
PASO 3: Pero es posible que no encuentre el máximo encontrado anteriormente en la matriz dada, por lo tanto, coincida tanto como pueda desde el bit más significativo al bit menos significativo. esto tomará O (N log N). Al hacer esto para todos los números, obtienes el máximo xor de dos números en la matriz dada. Luego encuentre el máximo de todos estos valores. Esto es (O (N)).

Por lo tanto, la complejidad es O (NlogN) + O (NlogN) + O (N) ~ O (NlogN)
Explicará detalles si lo necesita …,

Créditos: aprendí de mis maestros

Complejidad de tiempo: O (n)

La idea de este algoritmo es :
para determinar iterativamente cuál sería cada bit del resultado final de izquierda a derecha. Y reduce la iteración del grupo candidato por iteración. por ejemplo, supongamos que la entrada es a, b, c, d, … z, 26 enteros en total. En la primera iteración, si descubrió que a, d, e, h, u difieren en el MSB (bit más significativo), entonces está seguro de que el MSB del resultado final está establecido. Ahora, en la segunda iteración, intenta ver si entre a, d, e, h, u hay al menos dos números que hacen que el segundo MSB difiera, si es así, definitivamente, el segundo MSB se establecerá en el resultado final. Y tal vez en este punto el grupo candidato pasa de a, d, e, h, u a a, e, h. Implícitamente, en cada iteración, estás reduciendo el grupo de candidatos, pero no necesitas rastrear cómo se está reduciendo el grupo, solo te importa el resultado final.

  Solución de clase pública {
     public int findMaximumXOR (int [] nums) {
         int max = 0, máscara = 0;
         para (int i = 31; i> = 0; i -) {
             máscara = máscara |  (1 << i);
             Establecer  set = new HashSet <> ();
             para (int num: nums) {
                 set.add (número y máscara);
             }
             int tmp = max |  (1 << i);
             for (int prefix: set) {
                 if (set.contains (tmp ^ prefijo)) {
                     max = tmp;
                     descanso;
                 }
             }
         }
         retorno max;
     }
 }

Algoritmos: ¿Cómo podemos encontrar dos índices i y j en una matriz A [1 … n] de enteros de modo que A [i] ^ A [j] sea máximo en tiempo subcuadrático?

Sin embargo, esto no es técnicamente NLogN. Si el elemento máximo de la matriz es P, esto es NLogP

Si desea encontrar solo el valor máximo, aquí está el código de Python …
En este código, he tenido en cuenta que se me da un rango de números con ‘l’ como límite inferior y ‘r’ como límite superior y no falta ningún número en b / w. Puede hacer lo mismo con su matriz ordenándola. Excluyendo la complejidad de la clasificación, mi código es O (const):

def maxXor (l, r):
matemática de importación, operador
d = operador.xor (l, r)
n = math.log (d, 2)
o = math.ceil (n)
res = (2 ** o) -1
res = “%. 0f”% res
volver res
_l = int (raw_input ());
_r = int (raw_input ());
res = maxXor (_l, _r);
imprimir (res)

El código funciona en 2 tricls pequeños:
1) – max y min nums ‘xor le dará la idea del rango de valores xor.
2) – solo necesita encontrar el siguiente número que sea acorde con ((2 ^ n) -1). ese num es el valor máximo de xor en ese rango.

p.ej. 500 y 544
cuando xor 500 y 544 obtenemos 980. Esto significa que max xor en este rango será 1023, es decir (1024-1) o (2 ^ 10-1)
El código mencionado anteriormente hace lo mismo